樹結(jié)構(gòu)在程序設(shè)計中的運用

1、樹結(jié)構(gòu)在程序設(shè)計中的運用OICF-信息學(xué)奧林匹克綜合論壇http:/oicf.bbs.tc/樹結(jié)構(gòu)在程序設(shè)計中的運用引言一并查集二線段樹三樹狀數(shù)組小結(jié)引言引言近年來，由于各種競賽紛紛采用free-pascal，因此對于算法來說，空間效率上的要求降低了，而對時間效率卻提出了更高的要求。這使得選手不僅要嫻熟地掌握常規(guī)算法，而且要大膽創(chuàng)新，構(gòu)造更高效的算法來解決問題。在以往的程序設(shè)計中，鏈?zhǔn)浇Y(jié)構(gòu)采用得較多。的確鏈?zhǔn)浇Y(jié)構(gòu)有編程復(fù)雜度低、簡單易懂等優(yōu)點，但有一個致命的弱點：相鄰的兩個元素間的聯(lián)系并不明顯。而樹結(jié)構(gòu)卻能很好的做到這一點。 返回并查集并查集競賽中會經(jīng)常遇到這樣的題目：給出各個元素之間的聯(lián)系，

2、要求競賽中會經(jīng)常遇到這樣的題目：給出各個元素之間的聯(lián)系，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。合稱為并查集。鏈結(jié)構(gòu)的并查集樹結(jié)構(gòu)的并查集鏈結(jié)構(gòu)的并查集鏈結(jié)構(gòu)的并查集鏈表被普通用來計算并查集：表中的每個元素設(shè)兩個指針：一個鏈表被普通用來計算并查集：表中的每個元素設(shè)兩個指針：一個指向同一集合中的下一個元素；另一個指向表首元素。采用鏈?zhǔn)街赶蛲患现械南乱粋€元素；另一個指向表首元素。采用鏈?zhǔn)酱鎯?/p>

3、結(jié)構(gòu)，在進(jìn)行集合的查找時的算法復(fù)雜度僅為存儲結(jié)構(gòu)，在進(jìn)行集合的查找時的算法復(fù)雜度僅為O O（1 1）；但合）；但合并集合時的算法復(fù)雜度卻達(dá)到了并集合時的算法復(fù)雜度卻達(dá)到了O O（n n）。如果我們希望兩種基本）。如果我們希望兩種基本操作的時間效率都比較高的話，鏈?zhǔn)酱鎯Ψ绞骄筒僮鞯臅r間效率都比較高的話，鏈?zhǔn)酱鎯Ψ绞骄汀傲Σ粡男牧Σ粡男摹绷?。了?返回樹結(jié)構(gòu)的并查集樹結(jié)構(gòu)的并查集采用樹結(jié)構(gòu)支持并查集的計算能夠滿足我們的要求。并查集與一采用樹結(jié)構(gòu)支持并查集的計算能夠滿足我們的要求。并查集與一般的樹結(jié)構(gòu)不同，每個頂點紀(jì)錄的不是它的子結(jié)點，而是將它的般的樹結(jié)構(gòu)不同，每個頂點紀(jì)錄的不是它的子結(jié)點，而是將它

4、的父結(jié)點記錄下來。下面我介紹一下樹結(jié)構(gòu)的并查集的兩種運算方父結(jié)點記錄下來。下面我介紹一下樹結(jié)構(gòu)的并查集的兩種運算方式式n直接在樹中查詢n邊查詢邊“路徑壓縮”對應(yīng)與前面的鏈?zhǔn)酱鎯Y(jié)構(gòu)，樹狀結(jié)構(gòu)的優(yōu)勢非常明顯：編程復(fù)雜度低；時間效率高。 返回直接在樹中查直接在樹中查詢詢集合的合并算法很簡單，只要將兩棵樹的根結(jié)點相連即可，集合的合并算法很簡單，只要將兩棵樹的根結(jié)點相連即可，這步操作只要這步操作只要O O（1 1）時間復(fù)雜度。所以算法的時間效率取決于集）時間復(fù)雜度。所以算法的時間效率取決于集合查找的快慢。而集合的查找效率與樹的深度呈線性關(guān)系。因此合查找的快慢。而集合的查找效率與樹的深度呈線性關(guān)系。因此

5、直接查詢所需要的時間復(fù)雜度平均為直接查詢所需要的時間復(fù)雜度平均為O O（logNlogN）。但在最壞情況下，）。但在最壞情況下，樹退化成為一條鏈，使得每一次查詢的算法復(fù)雜度為樹退化成為一條鏈，使得每一次查詢的算法復(fù)雜度為O O（N N）。）。邊邊查查詢邊詢邊“路徑壓縮路徑壓縮” 其實，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用其實，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用“路徑壓縮路徑壓縮”算法。它的想法很簡單：在集合的查找過程中順?biāo)惴?。它的想法很簡單：在集合的查找過程中順便將樹的深度降低。采用路徑壓縮后，每一次查詢所用的時間便將樹的深度降低。采用路徑壓縮后，每一次查詢所用的時間復(fù)雜

6、度為增長極為緩慢的復(fù)雜度為增長極為緩慢的ackermanackerman函數(shù)的反函數(shù)函數(shù)的反函數(shù)（x x）。）。對于可以想象到的對于可以想象到的n n，（n n）都是在）都是在5 5之內(nèi)的。之內(nèi)的。返回線段樹線段樹處理涉及到圖形的面積、周長等問題的時候，并不需要依賴很深處理涉及到圖形的面積、周長等問題的時候，并不需要依賴很深的數(shù)學(xué)知識，但要提高處理此類問題的效率卻又十分困難。這就的數(shù)學(xué)知識，但要提高處理此類問題的效率卻又十分困難。這就需要從根本上改變算法的基礎(chǔ)需要從根本上改變算法的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。這里要說的就是一數(shù)據(jù)結(jié)構(gòu)。這里要說的就是一種特殊的數(shù)據(jù)結(jié)構(gòu)種特殊的數(shù)據(jù)結(jié)構(gòu)線段樹線段樹。先看一道較基

7、礎(chǔ)的題目：先看一道較基礎(chǔ)的題目：給出區(qū)間上的給出區(qū)間上的n n條線段，判斷這些線段條線段，判斷這些線段覆蓋到的區(qū)間大小。覆蓋到的區(qū)間大小。通過這題我們來逐步認(rèn)識線段樹。通過這題我們來逐步認(rèn)識線段樹。線段樹的定義在線段樹中加入和刪除線段計算測度和連續(xù)線段數(shù) 返回線段樹的定義線段樹的定義線段樹是一棵二叉樹，將一個區(qū)間劃分為一個個i，i+1的單元區(qū)間，每個單元區(qū)間對應(yīng)線段樹中的一個葉子結(jié)點。每個結(jié)點用一個變量count來記錄覆蓋該結(jié)點的線段條數(shù)。區(qū)間區(qū)間11，77所對應(yīng)的線段樹如下圖所示。區(qū)間上有一條線段所對應(yīng)的線段樹如下圖所示。區(qū)間上有一條線段33，66。在線段樹中插入和刪除線段在線段樹中插入和刪

8、除線段在線段樹中插入和刪除線段的方法類似，都采用遞歸逐層向兩個在線段樹中插入和刪除線段的方法類似，都采用遞歸逐層向兩個子結(jié)點掃描，直到線段能夠蓋滿結(jié)點表示的整個區(qū)間為止。子結(jié)點掃描，直到線段能夠蓋滿結(jié)點表示的整個區(qū)間為止。經(jīng)過分析可以發(fā)現(xiàn)：在線段樹中插入、刪除線段的時間復(fù)雜度均為O（logN）。計算測度和連續(xù)線段數(shù)計算測度和連續(xù)線段數(shù)結(jié)點的測度結(jié)點的測度m m指的是結(jié)點所表示區(qū)間中線段覆蓋過的長度。指的是結(jié)點所表示區(qū)間中線段覆蓋過的長度。 j-i (count0）m= (count=0 且結(jié)點為葉結(jié)點) lch + rch(count=0 且結(jié)點為內(nèi)部結(jié)點)連續(xù)線段數(shù)連續(xù)線段數(shù)lineline

9、指的是區(qū)間中互不相交的線段條數(shù)。指的是區(qū)間中互不相交的線段條數(shù)。連續(xù)線段數(shù)并不能像測度那樣將兩個子結(jié)點中的連續(xù)線段數(shù)簡單相加。于是我們引進(jìn)了兩個量lbd，rbd，分別表示區(qū)間的左右兩端是否被線段覆蓋。 1(左端點被線段覆蓋到)lbd = 0(左端點不被線段覆蓋到) 1 (右端點被線段覆蓋到)rbd = 0 (右端點不被線段覆蓋到)計算測度和連續(xù)線段數(shù)計算測度和連續(xù)線段數(shù)line可以根據(jù)lbd，rbd定義如下： 1 (count 0) 0 (count=0 且結(jié)點為葉結(jié)點) Line= lch.Line + rch.Line - 1 (count=0 且結(jié)點為內(nèi)部結(jié)點，lchrbd、rchlbd

10、都為1) lch.Line + rch.Line (count=0且結(jié)點為內(nèi)部結(jié)點， lchrbd,rchLbd不同時為1) 計算測度和連續(xù)線段數(shù)計算測度和連續(xù)線段數(shù)返回Lbd=1rbd=1樹狀數(shù)組樹狀數(shù)組IOI2001IOI2001中的中的MOBILEMOBILE難倒了很多選手。雖然該題的題意十分簡單：難倒了很多選手。雖然該題的題意十分簡單：在一個矩陣中，通過更新元素值修改矩陣狀態(tài)，并計算某子矩陣在一個矩陣中，通過更新元素值修改矩陣狀態(tài)，并計算某子矩陣的數(shù)字和，但難點在于數(shù)據(jù)的規(guī)模極大。下面，我來介紹一種新的數(shù)字和，但難點在于數(shù)據(jù)的規(guī)模極大。下面，我來介紹一種新的數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)樹狀數(shù)組樹

11、狀數(shù)組。1、建立樹狀數(shù)組、建立樹狀數(shù)組C2、更新元素值、更新元素值3、子序列求和、子序列求和利用樹狀數(shù)組，編程的復(fù)雜度提高了，但程序的時間效率也大幅地提高。這正是利用了樹結(jié)構(gòu)能夠減少搜索范圍，將信息集中起來的優(yōu)點，讓更新數(shù)組和求和運算牽連盡量少的變量。 返回建立樹狀數(shù)組建立樹狀數(shù)組C C先將問題簡化，考察一維子序列求和的算法。設(shè)該序列為先將問題簡化，考察一維子序列求和的算法。設(shè)該序列為a1a1，a2ana2an算法算法1 1：直接在原序列中計算。顯然更新元素值的時間復(fù)雜度為：直接在原序列中計算。顯然更新元素值的時間復(fù)雜度為O(1)O(1)；在最壞情況下，子序列求和的時間復(fù)雜度為；在最壞情況下，

12、子序列求和的時間復(fù)雜度為(n)(n)。以上兩種算法，要么在更新元素值上耗費時間過長（算法1），要么在子序列求和上無法避免大量運算（算法2）。有沒有更好的方法呢？算法算法2 2：增加數(shù)組：增加數(shù)組b b，其中，其中bibia1+a2+aia1+a2+ai。由于。由于aiai的更改影響的更改影響bibnbibn，因此在最壞情況下更新元素值的算法復(fù)，因此在最壞情況下更新元素值的算法復(fù)雜度為雜度為O(n)O(n)；而子序列求和的算法復(fù)雜度僅為；而子序列求和的算法復(fù)雜度僅為O(1)O(1)。算法三：增加數(shù)組算法三：增加數(shù)組C C，其中，其中Ci=ai-2Ci=ai-2k k+1+ai(k+1+ai(k為

13、為i i在二進(jìn)制形在二進(jìn)制形式下末尾式下末尾0 0的個數(shù)的個數(shù)) )。由。由c c數(shù)組的定義可以得出數(shù)組的定義可以得出：c1=a1c1=a1c2=a1+a2=c1+a2c2=a1+a2=c1+a2c3=a3c3=a3c4=a1+a2+a3+a4=c2+c3+a4c4=a1+a2+a3+a4=c2+c3+a4c5=a5c5=a5c6=a5+a6=c5+a6c6=a5+a6=c5+a6在統(tǒng)計更新元素值和子序列求和的算法復(fù)雜度后，會發(fā)現(xiàn)兩種操作的時間復(fù)雜度均為（logN），大大提高了算法效率。返回c c數(shù)組的結(jié)構(gòu)對應(yīng)一棵樹，因此稱之為樹狀數(shù)組。數(shù)組的結(jié)構(gòu)對應(yīng)一棵樹，因此稱之為樹狀數(shù)組。更新元素值更新

14、元素值定理定理若若akak所牽動的序列為所牽動的序列為CpCp1 1 ，CpCp2 2CpCpm m 。則則p p1 1=k=k，而，而p p i+1 i+1=p=pi i+2+2lili（l li i為為p pi i在二進(jìn)制中末尾的個數(shù)）。在二進(jìn)制中末尾的個數(shù)）。由此得出更改元素值的方法：若將由此得出更改元素值的方法：若將x x添加到添加到akak，則，則c c數(shù)組中數(shù)組中cpcp1 1 、cpcp2 2 、cpcpm m （p pm mnpn9 由此得出，c3、c4、c8亦應(yīng)該添加x。 返回引引理理 若 ak所牽動的序列為 Cp1，Cp2 Cpm， 且 p1 p2 pm ，則有 l1 l2

15、 lm（li為 pi在二進(jìn)制中末尾的個數(shù)） 。 證證明明： 若存在某個 i 有 lili+1，則 pi-2 li +1kpi，pi+1-2li+1+1kpi+1，pi+1 2 Li+1+1kpi，即 Pi+1Pi+2Li+1 1 (1) 而由 Li=Li+1、Pi Pi+1可得 Pi+1 Pi + 2Li (2) (1) (2)矛盾，可知 l1 l2 lm 定定理理 p1=k，而 p i+1=pi+2li 證證明明： 因為 p1 p2 li 的數(shù)（若出現(xiàn) Pi+x 比 pi+1更小，則 x2li ，與 x 在二進(jìn)制中的位數(shù)小于 li相矛盾） 。Pi+1=pi+2li，li+1li+1。 由 p

16、i-2li+1KPi可知，Pi+1-2li+1+1Pi+2li2*2li+1=Pi 2li+1KPiP i+1 ，故Pi與 pi+1之間的遞推關(guān)系式為 P i+1=Pi+2li 子序列求和子序列求和子序列求和可以轉(zhuǎn)化為求由子序列求和可以轉(zhuǎn)化為求由a1a1開始的序列開始的序列a1aka1ak的和的和S S。而在樹狀數(shù)組中求而在樹狀數(shù)組中求S S十分簡單：十分簡單： 根據(jù)根據(jù)ck=ak-2ck=ak-2l l+1+ +ak (l+1+ +ak (l為為k k在二進(jìn)制數(shù)中末尾的個數(shù)在二進(jìn)制數(shù)中末尾的個數(shù)) )我們從我們從k k1 1=k=k出發(fā)，按照出發(fā)，按照k ki+1i+1=k=ki i- -2 2lkilki（lkilki為為k ki i在二進(jìn)制數(shù)中末尾在二進(jìn)制數(shù)中末尾0 0的個數(shù)）的個數(shù)） 公式一公式一遞推遞推k k2 2，k k3 3，k km m (k (km+1m+1=0)=0)。由此得出。由此得出S=ckS=ck1 1+ck+ck2 2+ck+ck3 3 + + ck + + ckm m 例如，計算a1+a2+a3+a4+a5+a6+a7k1=7k2= k1-2l1=7-20=6k3= k2-2l2=6-21=4k4= k3-2l3=4-22=0 即a1+a2+ a3+a4+ a5+a6+ a7=c7+c6+c4子矩陣求和子矩陣求和返回推廣到二維，同樣也