1、線段線段樹是建立段的基礎上，每個結點都代表了一條線段a , b。長度為 的線段成為元線段。非元線段都有兩個子結點，左結點代表的線段為aa + b ) / 2，右結點代表的線段為 ( a + b ) / 2 , b。右圖就是一棵長度范圍為1 , 10長度范圍為1 , L 的一棵線段樹的深度為 log ( L - 1 ) + 1。這個顯然，而且一棵線段樹的空間復雜度為 O（L）。線段樹支持最基本的操作為線段線段樹是建立段的基礎上，每個結點都代表了一條線段a , b。長度為 的線段成為元線段。非元線段都有兩個子結點，左結點代表的線段為aa + b ) / 2，右結點代表的線段為 ( a + b )

2、/ 2 , b。右圖就是一棵長度范圍為1 , 10長度范圍為1 , L 的一棵線段樹的深度為 log ( L - 1 ) + 1。這個顯然，而且一棵線段樹的空間復雜度為 O（L）。線段樹支持最基本的操作為和刪除一條線段。下面為例，詳細敘述，將一條線段a , 到代表線段l , r的結點 p 中，如果 p mid（lr）/2。如果 amid，那么將線段a , b 到 p 的右兒子結點中。（刪除）操作的時間復雜度為 O （ Log n ）上面的都是些基本的線段樹結構，但只有這些并不能做什么，就好比一個程序有輸入沒輸出，根本沒有任何用處。最簡單的應用就是線段有否被覆蓋，并隨時查詢當前被覆蓋線段的總長度

3、。那么此時可以在結點結構中加入一個變量count蓋的線段長度和。這樣就要（刪除）當總值就是根節點的 count 值了。這個 count 另外也可以將 count 換成 bool cover；支持查找一個結點或線段是否被覆蓋。相信對算法設計或者數據結構有一定了解的人對線段樹都不會太陌生。它是能夠在 log(MaxLen)時間內完成線段的添加、刪除、查詢等操作。但一般的實現都有點復雜而線段樹應用中有一種是專門針對點的。（點樹？）它的實現卻非常簡單。先來考慮一下下面的需求（全部要求在 LogN 時間這種數據結構用？內完成）：如何知道一個點在一個點集里的大小”？很簡單，開一個點數組，排個序，再二分查找

4、就行了；如何在一個點集內動態增刪點？也很簡單，弄個平衡樹就行了（本來平衡樹比線段樹復雜得多，但自從世界上有了 STL set這么個好東東，就_）那如果我既要動態增刪點，也要隨時查詢到一個點的可能就要出動到的“點樹”了。其實現原理很簡單：每當增加（或刪除）一個大小為 X 的點時，就在樹上添加（呢？那對不起，刪除）一條(X,MaxLen)的線段（不含端點），當要查詢一個點的時，只要看看其上有多少條線段就可以了。針對這一需求，這里有個非常簡單的實現（十多行，夠短了吧？）其中 clear()用于清空點集； add()用于添加一個點；cntLs()回小于 n 的點的個數，也就是 n ，類似地 cntGt

5、 。用呢？其中一個應用時在 O(NlogN)時間內求出一個排列的逆序這個點樹數（?=1484，你有更好的算法嗎？歡迎tGt(x);然后再 add(x)交流）方法是每讀到一個數 x，就讓逆序數這個實現還可以進行一些擴展。比如刪除 n)，只要把 n)中的ize 換成-size，把 ai/2+改成 ai/2-即可。另外還可以通過二分查找功能在 N)時間內查到補充第 n 的點的大小。應該也可以三四行內搞定。同學在 2008年信息學奧賽冬令營上新發明了一種線段樹的省空間堆式法,具體方法可以見 08 年冬令營課件template 用呢？其中一個應用時在 O(NlogN)時間內求出一個排列的逆序這個點樹數（

6、?=1484，你有更好的算法嗎？歡迎tGt(x);然后再 add(x)交流）方法是每讀到一個數 x，就讓逆序數這個實現還可以進行一些擴展。比如刪除 n)，只要把 n)中的ize 換成-size，把 ai/2+改成 ai/2-即可。另外還可以通過二分查找功能在 N)時間內查到補充第 n 的點的大小。應該也可以三四行內搞定。同學在 2008年信息學奧賽冬令營上新發明了一種線段樹的省空間堆式法,具體方法可以見 08 年冬令營課件template N / 表示可用區間為0,N)N 2 的冪數class PoTree a 2 * N;ifor clear() memset( this , 0 , siz

7、eof ( * this ); n) = N + n; + + a; i ; i /= 2 / 2 + if ( i & 1 ) i = for + 2統計小于; / 若統計小于等于則 )/ 2 if (i & 1 ) c += ai return c;n) return size - aN + n - void n)for(-an; n1; /*/* 解決：求點集中第 i 小的數(0 數起* 注意：如果 i=size N-if(na) else n-=a, return i-/if(na) else n-=a, return i-/T t;main()else cinreturn 另一種功能上比較類似的數據結構：“樹狀數組”。它們有不少相似之處：針對點集的處理（添加、刪除、查找）；相似的時空復雜度（logN 時間，2N 空間相似的編程復雜度（都比