三等分線段

相信對算法設(shè)計或者數(shù)據(jù)結(jié)構(gòu)有一定了解的人對線段樹都不會太陌生。它是能夠在log(MaxLen)時間內(nèi)完成線段的添加、刪除、查詢等操作。但一般的實現(xiàn)都有點復雜而線段樹應用中有一種是專門針對點的。(點樹?)它的實現(xiàn)卻非常簡單。

這種數(shù)據(jù)結(jié)構(gòu)有什么用?我們先來考慮一下下面的需求(全部要求在LogN時間內(nèi)完成):如何知道一個點在一個點集里的大小"排名"?很簡單，開一個點數(shù)組，排個序，再二分查找就行了;如何在一個點集內(nèi)動態(tài)增刪點?也很簡單，弄個平衡樹就行了(本來平衡樹比線段樹復雜得多，但自從世界上有了STL set這么個好東東，就……^_^)那如果我既要動態(tài)增刪點，也要隨時查詢到一個點的排名呢?那對不起，可能就要出動到我們的"點樹"了。

其實現(xiàn)原理很簡單:每當增加(或刪除)一個大小為X的點時，就在樹上添加(或刪除)一條(X,MaxLen)的線段(不含端點)，當要查詢一個點的排名時，只要看看其上有多少條線段就可以了。針對這一需求，這里有個非常簡單的實現(xiàn)(見以下代碼，十多行，夠短了吧?)其中clear()用于清空點集;add()用于添加一個點;cntLs()返回小于n的點的個數(shù)，也就是n的升序排名，類似地cntGt是降序排名。

這個點樹有什么用呢?其中一個應用是在O(NlogN)時間內(nèi)求出一個排列的逆序數(shù)，方法是每讀到一個數(shù)x，就讓逆序數(shù)+=cntGt(x);然后再add(x)。

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

補充:楊弋同學在2008年信息學奧賽冬令營上新發(fā)明了一種線段樹的省空間堆式存儲法，具體方法可以見08年冬令營課件.

實現(xiàn)代碼及測試程序

另一種功能上比較類似的數(shù)據(jù)結(jié)構(gòu):"樹狀數(shù)組"。它們有不少相似之處:

針對點集的處理(添加、刪除、查找);

相似的時空復雜度(logN時間，2N空間);

相似的編程復雜度(都比線段樹簡短得多);

因此，所有可以用樹狀數(shù)組解決的問題都可以用這個"點樹"來解決，另外它還有以下好處:

更直觀的轉(zhuǎn)移;

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

ZKW線段樹由清華大學張昆瑋發(fā)現(xiàn)，是一種新的用非遞歸方式實現(xiàn)的線段樹，具體請參考張昆瑋先生本人的講稿《統(tǒng)計的力量》 。

線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個區(qū)間劃分成一些單元區(qū)間，每個單元區(qū)間對應線段樹中的一個葉結(jié)點。

對于線段樹中的每一個非葉子節(jié)點[a,b]，它的左兒子表示的區(qū)間為[a,(a+b)/2]，右兒子表示的區(qū)間為[(a+b)/2+1,b]。因此線段樹是平衡二叉樹，最后的子節(jié)點數(shù)目為N，即整個線段區(qū)間的長度。

使用線段樹可以快速的查找某一個節(jié)點在若干條線段中出現(xiàn)的次數(shù)，時間復雜度為O(logN)。而未優(yōu)化的空間復雜度為2N，因此有時需要離散化讓空間壓縮。

線段樹至少支持下列操作:

Insert(t,x):將包含在區(qū)間 int 的元素 x 插入到樹t中;

Delete(t,x):從線段樹 t 中刪除元素 x;

Search(t,x):返回一個指向樹 t 中元素 x 的指針。