线段树
线段树
线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。长度为1的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。
右图就是一棵长度范围为[1 , 10]的线段树。
长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。这个显然，而且存储一棵线段树的空间复杂度为O（L）。
线段树支持最基本的操作为插入和删除一条线段。下面已插入为例，详细叙述，删除类似。
将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。如果a<mid，那么将线段[a , b] 也插入到p的左儿子结点中，如果b>mid，那么将线段[a , b] 也插入到p的右儿子结点中。
插入（删除）操作的时间复杂度为O （ Log n ）。
上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。
最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。
另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。[1]
相信对算法设计或者数据结构有一定了解的人对线段树都不会太陌生。它是能够在log(MaxLen)时间内完成线段的添加、删除、查询等操作。但一般的实现都有点复杂而线段树应用中有一种是专门针对点的。（点树？）它的实现却非常简单。
这种数据结构有什么用？我们先来考虑一下下面的需求（全部要求在LogN时间内完成）：如何知道一个点在一个点集里的大小“排名”？很简单，开一个点数组，排个序，再二分查找就行了；如何在一个点集内动态增删点？也很简单，弄个平衡树就行了（本来平衡树比线段树复杂得多，但自从世界上有了STL set这么个好东东，就……^_^）那如果我既要动态增删点，也要随时查询到一个点的排名呢？那对不起，可能就要出动到我们的“点树”了。
其实现原理很简单：每当增加（或删除）一个大小为X的点时，就在树上添加（或删除）一条(X,MaxLen)的线段（不含端点），当要查询一个点的排名时，只要看看其上有多少条线段就可以了。针对这一需求，这里有个非常简单的实现（见以下代码，十多行，够短了吧？）其中clear()用于清空点集；add()用于添加一个点；cntLs()返回小于n的点的个数，也就是n的升序排名，类似地cntGt是降序排名。
这个点树有什么用呢？其中一个应用时在O(NlogN)时间内求出一个排列的逆序数（http://acm.zju.edu.cn/show_problem.php?pid=1484，你有更好的算法吗？欢迎交流）方法是每读到一个数x，就让逆序数+=cntGt(x);然后再add(x)。
这个实现还可以进行一些扩展。比如删除del(int n)，只要把add(int n)中的++size换成--size，把a[i/2]++改成a[i/2]--即可。另外还可以通过二分查找功能在O(logN)时间内查到排名第n的点的大小。应该也可以三四行内搞定。
补充:杨弋同学在2008年信息学奥赛冬令营上新发明了一种线段树的省空间堆式存储法,具体方法可以见08年冬令营课件.
template < int N > // 表示可用区间为[0,N)，其中N必须是2的幂数;
class PointTree {
int a[ 2 * N];
int size;
void clear() { memset( this , 0 , sizeof ( * this ));}
void add( int n) {
int i = N + n; ++ size;
for ( ++ a; i > 1 ; i /= 2 )
if ( ~ i & 1 ) a[i / 2 ] ++ ;
}
int cntLs( int n) { // 统计小于
int i = N + n,c = 0 ; // 若统计小于等于则c=a;
for (; i > 1 ; i /= 2 )
if (i & 1 ) c += a[i / 2 ];
return c;
}
int cntGt( int n) { return size - a[N + n] - cntLs(n); }
} ;
void del(int n){
if(!a[n+=N])return;
--size;
for(--a[n]; n>1; n/=2)
if(~n&1)--a[n/2];
}
/**//* 解决：求点集中第i小的数(由0数起)
* 注意：如果i>=size 返回N-1
*/
int operator[](int n){
int i=1;
while(i<N){
if(n<a) i*=2;
else n-=a, i=i*2+1;
}
return i-N;
}
};
//附一个测试程序
#include<iostream.h>
T<8192> t;
int main(){
char c; int n;
while(cin>>c){
if(c=='c') t.clear();
else{
cin>>n;
if(c=='a') t.add(n);
if(c=='d') t.del(n);
if(c=='q') cout<<t[n]<<endl;
}
}
return 0;
}
另一种功能上比较类似的数据结构：“树状数组”。它们有不少相似之处：
针对点集的处理（添加、删除、查找）；
相似的时空复杂度（logN时间，2N空间）；
相似的编程复杂度（都比线段树简短得多）；
因此，所有可以用树状数组解决的问题都可以用这个“点树”来解决，另外它还有以下好处：
更直观的转移；
同时支持自下而上和自上而下两种方向的查找和更新，而后者树状数组不支持，所以树状数组不提供某些功能，比如说O(logN)求点集中第k小数。