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

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

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

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

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

6、?=1484，你有更好的算法嗎？歡迎tGt(x);然后再 add(x)交流）方法是每讀到一個數(shù) x，就讓逆序數(shù)這個實現(xiàn)還可以進行一些擴展。比如刪除 n)，只要把 n)中的ize 換成-size，把 ai/2+改成 ai/2-即可。另外還可以通過二分查找功能在 N)時間內(nèi)查到補充第 n 的點的大小。應(yīng)該也可以三四行內(nèi)搞定。同學(xué)在 2008年信息學(xué)奧賽冬令營上新發(fā)明了一種線段樹的省空間堆式法,具體方法可以見 08 年冬令營課件template N / 表示可用區(qū)間為0,N)N 2 的冪數(shù)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統(tǒng)計小于; / 若統(tǒng)計小于等于則 )/ 2 if (i & 1 ) c += ai return c;n) return size - aN + n - void n)for(-an; n1; /*/* 解決：求點集中第 i 小的數(shù)(0 數(shù)起* 注意：如果 i=size N-if(na) else n-=a, return i-/if(na) else n-=a, return i-/T t;main()else cinreturn 另一種功能上比較類似的數(shù)據(jù)結(jié)構(gòu)：“樹狀數(shù)組”。它們有不少相似之處：針對點集的處理（添加、刪除、查找）；相似的時空復(fù)雜度（logN 時間，2N 空間相似的編程復(fù)雜度（都比