點樹

點樹是能夠在log(MaxLen)時間內完成線段的添加、刪除、查詢等操作。其原理是其中一個套用時在O(NlogN)時間內求出一個排列的逆序數方法是每讀到一個數x，就讓逆序數+=cntGt(x);然後再add(x)。

相信對算法設計或者數據結構有一定了解的人對線段樹都不會太陌生。它是能夠在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++改成a--即可。另外還可以通過二分查找功能在O(logN)時間內查到排名第n的點的大小。應該也可以三四行內搞定。
template < int N > // 表示可用區間為&#91;0,N)，其中N必須是2的冪數;
class PointTree {
int a&#91; 2 * N&#93;;
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&#91;i/2&#93; ++ ;
}
int cntLs( int n) { // 統計小於
int i = N + n,c = 0 ; // 若統計小於等於則c=a;
for (; i > 1 ; i /= 2 )
if (i & 1 ) c += a&#91;i/2&#93;;
return c;
}
int cntGt( int n) { return size - a&#91;N + n&#93; - cntLs(n); }
} ;
嗯~~~為了解http://acm.zju.edu.cn/show_problem.php?pid=2425這一題，還是把上述兩個擴展給實現了啦，果然不難： （接上）
void del(int n){
if(!a&#91;n+=N&#93;)return;
--size;
for(--a&#91;n&#93;; n>1; n/=2)
if(~n&1)--a&#91;n/2&#93;;
}
/**//* 解決：求點集中第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==&#039;c&#039;) t.clear();
else{
cin>>n;
if(c==&#039;a&#039;) t.add(n);
if(c==&#039;d&#039;) t.del(n);
if(c==&#039;q&#039;) cout<<t&#91;n&#93;<<endl;
}
}
return 0;
}
P.S.：
在寫完這篇文章一段時間後，我認識了另一種功能上比較類似的數據結構，叫做“樹狀數組”。它們有不少相似之處：
針對點集的處理（添加、刪除、查找）；
相似的時空複雜度（logN時間，2N空間）；
相似的編程複雜度（都比線段樹簡短得多）；
因此，所有可以用樹狀數組解決的問題都可以用這個“點樹”來解決，另外它還有以下好處：
更直觀的轉移（個人感受，不一定要同意）；
同時支持自下而上和自上而下兩種方向的查找和更新，而後者樹狀數組不支持，所以樹狀數組不提供某些功能，比如說O(logN)求點集中第k小數。