线段树的一种简化实现[原] by 踏雪赤兔

　　相信对算法设计或者数据结构有一定了解的人对线段树都不会太陌生。它是能够在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的点的大小。应该也可以三四行内搞定。

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];?i > 1 ;?i /= 2 )
???????????? if ( ~ i & 1 )?a[i / 2 ] ++ ;
????} ?
???? int ?cntLs( int ?n) { // 统计小于?
???????? int ?i = N + n,c = 0 ;? // 若统计小于等于则c=a[i];?
???????? 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])?i*=2;
????????????else?n-=a[i],?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;
}??

posted on 2006-09-13 19:54 踏雪赤兔 阅读(6) 评论(3)  编辑 收藏 收藏至365Key 所属分类: 玩转编程