线段树

线段树

线段树是一种 ​​二叉搜索树​​​，与 ​​​区间树​​相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非 ​​叶子节点​​​[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是 ​​​平衡二叉树​​，最后的子节点数目为N，即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数， ​​时间复杂度​​​为O(logN）。而未优化的 ​​​空间复杂度​​为2N，因此有时需要离散化让空间压缩。

线段树至少支持下列操作：

Insert(t,x）：将包含在区间 int 的 ​​元素​​ x 插入到树t中；

Delete(t,x）：从线段树 t 中删除元素 x；

Search(t,x）：返回一个指向树 t 中元素 x 的指针

没看懂

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。