ACM___________________________

 轉載自 http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html

相信對算法設計或者數據結構有一定了解的人對線段樹都不會太陌生。它是能夠在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;
}  

求點集里n的個數了!

int cntEQ(int n){
    return a[N+n];
}

• 針對點集的處理（添加、刪除、查找）；
• 相似的時空復雜度（logN時間，2N空間）；
• 相似的編程復雜度（都比線段樹簡短得多）；

因此，所有可以用樹狀數組解決的問題都可以用這個“點樹”來解決，另外它還有以下好處：

• 更直觀的轉移（個人感受，不一定要同意）；
• 同時支持自下而上和自上而下兩種方向的查找和更新，而后者樹狀數組不支持，所以樹狀數組不提供某些功能，比如說O(logN)求點集中第k小數。

posted on 2006-09-13 19:54 踏雪赤兔