网上找的一些线段树

1、线段线段树是建立段的基础上，每个结点都代表了一条线段a , b。长度为 的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为aa + b ) / 2，右结点代表的线段为 ( a + b ) / 2 , b。右图就是一棵长度范围为1 , 10长度范围为1 , L 的一棵线段树的深度为 log ( L - 1 ) + 1。这个显然，而且一棵线段树的空间复杂度为 O（L）。线段树支持最基本的操作为线段线段树是建立段的基础上，每个结点都代表了一条线段a , b。长度为 的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为aa + b ) / 2，右结点代表的线段为 ( a + b )

2、/ 2 , b。右图就是一棵长度范围为1 , 10长度范围为1 , L 的一棵线段树的深度为 log ( L - 1 ) + 1。这个显然，而且一棵线段树的空间复杂度为 O（L）。线段树支持最基本的操作为和删除一条线段。下面为例，详细叙述，将一条线段a , 到代表线段l , r的结点 p 中，如果 p mid（lr）/2。如果 amid，那么将线段a , b 到 p 的右儿子结点中。（删除）操作的时间复杂度为 O （ Log n ）上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。最简单的应用就是线段有否被覆盖，并随时查询当前被覆盖线段的总长度

3、。那么此时可以在结点结构中加入一个变量count盖的线段长度和。这样就要（删除）当总值就是根节点的 count 值了。这个 count 另外也可以将 count 换成 bool cover；支持查找一个结点或线段是否被覆盖。相信对算法设计或者数据结构有一定了解的人对线段树都不会太陌生。它是能够在 log(MaxLen)时间内完成线段的添加、删除、查询等操作。但一般的实现都有点复杂而线段树应用中有一种是专门针对点的。（点树？）它的实现却非常简单。先来考虑一下下面的需求（全部要求在 LogN 时间这种数据结构用？内完成）：如何知道一个点在一个点集里的大小”？很简单，开一个点数组，排个序，再二分查找

4、就行了；如何在一个点集内动态增删点？也很简单，弄个平衡树就行了（本来平衡树比线段树复杂得多，但自从世界上有了 STL set这么个好东东，就_）那如果我既要动态增删点，也要随时查询到一个点的可能就要出动到的“点树”了。其实现原理很简单：每当增加（或删除）一个大小为 X 的点时，就在树上添加（呢？那对不起，删除）一条(X,MaxLen)的线段（不含端点），当要查询一个点的时，只要看看其上有多少条线段就可以了。针对这一需求，这里有个非常简单的实现（十多行，够短了吧？）其中 clear()用于清空点集； add()用于添加一个点；cntLs()回小于 n 的点的个数，也就是 n ，类似地 cntGt

5、 。用呢？其中一个应用时在 O(NlogN)时间内求出一个排列的逆序这个点树数（?=1484，你有更好的算法吗？欢迎tGt(x);然后再 add(x)交流）方法是每读到一个数 x，就让逆序数这个实现还可以进行一些扩展。比如删除 n)，只要把 n)中的ize 换成-size，把 ai/2+改成 ai/2-即可。另外还可以通过二分查找功能在 N)时间内查到补充第 n 的点的大小。应该也可以三四行内搞定。同学在 2008年信息学奥赛冬令营上新发明了一种线段树的省空间堆式法,具体方法可以见 08 年冬令营课件template 用呢？其中一个应用时在 O(NlogN)时间内求出一个排列的逆序这个点树数（

6、?=1484，你有更好的算法吗？欢迎tGt(x);然后再 add(x)交流）方法是每读到一个数 x，就让逆序数这个实现还可以进行一些扩展。比如删除 n)，只要把 n)中的ize 换成-size，把 ai/2+改成 ai/2-即可。另外还可以通过二分查找功能在 N)时间内查到补充第 n 的点的大小。应该也可以三四行内搞定。同学在 2008年信息学奥赛冬令营上新发明了一种线段树的省空间堆式法,具体方法可以见 08 年冬令营课件template N / 表示可用区间为0,N)N 2 的幂数class PoTree a 2 * N;ifor clear() memset( this , 0 , siz

7、eof ( * this ); n) = N + n; + + a; i ; i /= 2 / 2 + if ( i & 1 ) i = for + 2统计小于; / 若统计小于等于则 )/ 2 if (i & 1 ) c += ai return c;n) return size - aN + n - void n)for(-an; n1; /*/* 解决：求点集中第 i 小的数(0 数起* 注意：如果 i=size N-if(na) else n-=a, return i-/if(na) else n-=a, return i-/T t;main()else cinreturn 另一种功能上比较类似的数据结构：“树状数组”。它们有不少相似之处：针对点集的处理（添加、删除、查找）；相似的时空复杂度（logN 时间，2N 空间相似的编程复杂度（都比