點樹

相信對算法設計或者數據結構有一定了解的人對線段樹都不會太陌生。它是能夠在log(MaxLen)時間內完成線段的添加、刪除、查詢等操作。但一般的實現都有點複雜（我自寫的是要遞歸的，比較多行）。而線段樹套用中有一種是專門針對點的。（點樹？）它的實現卻非常簡單。

基本介紹

• 中文名：點樹
• 實質：數據結構
• 功能：完成線段的添加、刪除、查詢
• 作用：隨時查詢到一個點的排名

基本簡介

這種數據結構有什麼用？我們先來考慮一下下面的需求（全部要求在LogN時間內完成）：如何知道一個點在一個點集裡的大小“排名”？很簡單，開一個點數組，排個序，再二分查找就行了；如何在一個點集內動態增刪點？也很簡單，弄個平衡樹就行了。那如果既要動態增刪點，也要隨時查詢到一個點的排名呢？那對不起，可能就要出動到我們的“點樹”了。

實現原理

每當增加（或刪除）一個大小為X的點時，就在樹上添加（或刪除）一條(X,MaxLen)的線段（不含端點），當要查詢一個點的排名時，只要看看其上有多少條線段就可以了。針對這一需求，這裡有個非常簡單的實現:其中clear()用於清空點集；add()用於添加一個點；cntLs()返回小於n的點的個數，也就是n的升序排名，類似地cntGt是降序排名。

這個點樹有什麼用呢？其中一個套用時在O(NlogN)時間內求出一個排列的逆序數方法是每讀到一個數x，就讓逆序數+=cntGt(x);然後再add(x)。

這個實現還可以進行一些擴展。比如刪除del(int n)，只要把add(int n)中的++size換成--size，把a[i/2]++改成a[i/2]--即可。另外還可以通過二分查找功能在O(logN)時間內查到排名第n的點的大小。應該也可以三四行內搞定。

template<intN>//表示可用區間為[0,N)，其中N必須是2的冪數;classPointTree{inta[2*N];intsize;voidclear(){memset(this,0,sizeof(*this));}voidadd(intn){inti=N+n;++size;for(++a;i>1;i/=2)if(~i&1)a[i/2]++;}intcntLs(intn){//統計小於inti=N+n,c=0;//若統計小於等於則c=a;for(;i>1;i/=2)if(i&1)c+=a[i/2];returnc;}intcntGt(intn){returnsize-a[N+n]-cntLs(n);}};

兩個擴展實現： （接上）

voiddel(intn){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*/intoperator[](intn){inti=1;while(i<N){if(n<a)i*=2;elsen-=a,i=i*2+1;}returni-N;}};

附一個測試程式

#include<iostream.h>T<8192>t;intmain(){charc;intn;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;}}return0;}

另一種功能上比較類似的數據結構，叫做“樹狀數組”。

針對點集的處理（添加、刪除、查找）；

相似的時空複雜度（logN時間，2N空間）；

相似的編程複雜度（都比線段樹簡短得多）；

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

更直觀的轉移（個人感受，不一定要同意）；

同時支持自下而上和自上而下兩種方向的查找和更新，而後者樹狀數組不支持，所以樹狀數組不提供某些功能，比如說O(logN)求點集中第k小數。