posts - 217, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

线段树Segment Tree

Posted on 2007-08-26 02:31 魔のkyo 阅读(1077) 评论(0)  编辑 收藏 引用 所属分类: DataStucture
//线段树,添加,删除,查询排名,查询第k小数都在O(logn)级,O(NlogN)时间内可求出一个排列的逆序数 example 1484,2425
//http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html 
template <int N> //表示可用区间为[0,N),其中N必须是2的幂数;
class PointTree{
    
int a[2*N];
    
int size;
public:
    
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 cntEQ(int n){return a[N+n];}
    
    
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;    
    }    
};
只有注册用户登录后才能发表评论。