算法合集之《數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率》

1、數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率從IOI98試題PICTURE談起福建師大附中 陳宏【關(guān)鍵字】數(shù)據(jù)結(jié)構(gòu)的選擇 線性結(jié)構(gòu) 樹形結(jié)構(gòu)【摘要】算法 + 數(shù)據(jù)結(jié)構(gòu)=程序。設(shè)計算法與選擇合適的數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計中相輔相成的兩方面，缺一不可。數(shù)據(jù)結(jié)構(gòu)的選擇一直是程序設(shè)計中的重點、難點，正確地應(yīng)用數(shù)據(jù)結(jié)構(gòu)，往往能帶來意想不到的效果。反之，如果忽視了數(shù)據(jù)結(jié)構(gòu)的重要性，對某些問題有時就得不到滿意的解答。通過對IOI98試題Picture的深入討論，我們可以看到兩種不同的數(shù)據(jù)結(jié)構(gòu)在解題中的應(yīng)用，以及由此得到的不同的算法效率。本文以Picture問題為例，探討數(shù)據(jù)結(jié)構(gòu)的選擇對算法效率的影響?！菊摹恳运惴ㄍǔＪ菦Q定程序效

2、率的關(guān)鍵，但一切算法最終都要在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)，許多算法的精髓就是在于選擇了合適的數(shù)據(jù)結(jié)構(gòu)作為基礎(chǔ)。在程序設(shè)計中，不但要注重算法設(shè)計，也要正確地選擇數(shù)據(jù)結(jié)構(gòu)，這樣往往能夠事半功倍。在算法時間與空間效率的兩方面，著重分析時間效率，即算法的時間復雜度，因為我們總是希望程序在較短的時間內(nèi)給出我們所希望的輸出。如果在空間上過于“吝嗇”而使得時間上無法承受，對解題并無益處。本文對IOI98的試題Picture作一些分析，通過兩種不同數(shù)據(jù)結(jié)構(gòu)的選擇，將了解到數(shù)據(jù)結(jié)構(gòu)對算法本身及算法效率的影響。Picture問題及算法設(shè)計一、 Picture問題Picture問題是IOI98的一道試題，描述如下：墻上貼

3、著一些海報、照片等矩形，所有的邊都為垂直或水平。每個矩形可以被其它矩形部分或完全遮蓋，所有矩形合并成區(qū)域的邊界周長稱為輪廓周長。例如圖1的三個矩形輪廓周長為30： 圖1要求編寫程序計算輪廓周長。數(shù)據(jù)量限制：0矩形數(shù)目<5000；坐標數(shù)值為整數(shù)，范圍是-10000，10000。二、 算法描述在算法的大體描述中，將不涉及到具體的數(shù)據(jù)結(jié)構(gòu)，便于數(shù)據(jù)結(jié)構(gòu)的進一步選擇和比較分析。（一） 、輪廓的定義在描述算法前，我們先明確一下“輪廓”的定義：1、輪廓由有限條線段組成，線段是矩形邊或者矩形邊的一部分。2、組成矩形邊的線段不應(yīng)被任何矩形遮蓋。圖2與圖3分別是遮蓋的兩種情況。 圖2 圖3 圖4 （AB被

4、遮蓋） （CD被遮蓋）（二） 、元線段本題的一大特征是分析矩形的邊，而邊的端點（即矩形的頂點）坐標為整數(shù)，且坐標取值范圍已經(jīng)限定在-10000，10000之間。這樣，就可以把這個平面理解成為一個網(wǎng)格。由于給出的坐標是整數(shù)，所以矩形邊一定在網(wǎng)格線上。在網(wǎng)格中，對于一條線段我們最關(guān)心其絕對坐標。如圖4，我們認為矩形邊AB由線段L1、L2、L3組成。像L1、L2、L3這樣連接相鄰網(wǎng)格頂點的基本線段，稱之為“元線段”，這樣就把矩形邊離散化了。顯然，有限的元線段覆蓋了所有的網(wǎng)格線，且元線段是組成矩形邊乃至組成輪廓的基本單位。一條元線段要么完全屬于輪廓，要么完全不屬于輪廓。這種定義使我們對問題的研究具體到

5、每一條元線段，這樣的離散化處理有利于問題的進一步討論。（三） 、超元線段元線段的引入，使問題更加具體。但也應(yīng)當看到，平面中共有20001*20000*2條元線段，研究的對象過多，而且計算量受到網(wǎng)格大小的影響，如果頂點坐標范圍是-1,000,000，1,000,000，元線段數(shù)目將達到8*1012，這是天文數(shù)字。因此有必要對“元線段”進行優(yōu)化。受到元線段的啟發(fā)，我們定義一種改進后的元線段“超元線段”，它將由對平面的“切割”得到。具體做法是，根據(jù)每個矩形縱向邊的橫坐標縱向地對平面進行2*N次切割、根據(jù)矩形橫向邊的縱坐標橫向地對矩形進行2*N次切割（N為矩形個數(shù)）。顯然，經(jīng)過切割后的平面被分成了(2

6、*N+1)2個區(qū)域，如圖5所示： 圖5 圖6其中像橫向邊AB、縱向邊CD這樣的線段就是“超元線段”。超元線段與元線段有著相似的性質(zhì)，也是組成輪廓的基本單位。所不同的是，超元線段的數(shù)目較少，一般為4*N條左右，且超元線段數(shù)目不受網(wǎng)格大小的影響?；诔€段的優(yōu)點，算法最終將研究超元線段。(一)、 離散化及算法框架算法的研究對象是超元線段，但這并不等于逐一枚舉，那樣耗時過大，而整體考慮又使得問題無從下手。有一種考慮方法是折中的，即既不研究每一條超元線段，也不同時研究所有的超元線段，而是再進一步優(yōu)化問題的離散化，即將超元線段分組研究。如圖6所示，夾在兩條縱向分割邊的超元線段自然地分為一組，它們的共同

7、點是長度相同，并且端點的橫坐標相同?？v向線段也可以進行類似的離散化。這樣的離散化處理后，使得問題規(guī)模降低，以此為基礎(chǔ)，算法的框架可以基本確定為： 1、對平面進行分割。 2、累加器ans ß 0。 3、研究每組超元線段，檢測其中屬于輪廓的部分的長度，并把這一長度累加入ans。 4、輸出ans的值。以上只是算法的基本框架，還很粗糙，求精部分有賴于數(shù)據(jù)結(jié)構(gòu)的具體選擇。三、 Picture問題的數(shù)據(jù)結(jié)構(gòu)選擇之一：線性結(jié)構(gòu)(一)、 映射結(jié)構(gòu)的建立算法的基礎(chǔ)是問題的離散化，要進行平面“分割”，一般需要記錄分割點，通常采用映射來記錄分割點。直觀的做法是采用一維數(shù)組形式，下標表示分割點的編號，數(shù)組元

8、素表示分割點的坐標。利用下標與數(shù)組元素的自然對應(yīng)，實現(xiàn)映射。應(yīng)該說，這樣表示是比較自然的，實現(xiàn)也比較方便。數(shù)組的優(yōu)點主要是存取方便，且可以在O(NlogN)時間內(nèi)排序。映射結(jié)構(gòu)定義如下： Type Mapped_TYPE = Object Len : 0.Max; 記下分割點的個數(shù) Coord : array1.Max of integer; 記下分割點坐標 Procedure Creat; 映射初始化 Procedure Insert(X : integer); 插入分割坐標X Procedure Sort; 對坐標排序End以下是三個過程的描述與解釋：Procedure Mapped_TY

9、PE.Creat1 Len ß 0Creat 用于初始化該映射Procedure Mapped_TYPE.Insert(X : Integer)1 Len ß Len + 12 CoordLen ß XInsert 用于插入一個分割坐標，此時坐標之間是無序的Procedure Mapped_TYPE.Sort略Sort 用于將Len個坐標排序。由于Coord是一維數(shù)組，Sort 容易實現(xiàn)，例如快速排序。設(shè)N = Len，Sort 效率可達O(NlogN)。針對整數(shù)，也可以采用筒排序得到更好的效率，但這不是問題的關(guān)鍵部分。 VarX_map, Y_map : Map

10、ped_TYPE 分別記錄橫縱坐標的映射 以橫坐標為例，在程序處理時，首先執(zhí)行X_map.Creat初始化映射。而后通過X_map.Insert將每個矩形縱向邊的橫坐標作為分割坐標插入X_map.Coord，最后執(zhí)行X_map.Sort進行排序。至此，映射建立完畢。應(yīng)該說，這一部分完全可以滿足算法要求，且執(zhí)行效率較高。三個過程中的Creat與Insert耗時均為O(1)，Sort耗時為O(NlogN)，但它只需執(zhí)行一次。(二)、 線性結(jié)構(gòu)的建立映射建立后，相當于完成了對平面的切割?，F(xiàn)在的主要問題是如何描述一組超元線段的狀態(tài)。由于最終要計算輪廓周長，我們最關(guān)心的是一組超元線段中究竟有多少條屬于輪

11、廓。由分組的方法可知，每組超元線段長度相同。以下均以橫向超元線段為例進行說明。設(shè)：超元線段組編號1N*2-1(N是矩形數(shù)目)編號為S的超元線段組中的線段長度為Length(S)編號為S的超元線段組中屬于圖形輪廓的超元線段數(shù)目為Belong(S)算式輪廓橫向邊周長ANS =則：其中Lenth(s)容易求得。如果超元線段組編號以網(wǎng)格中從左到右為原則，那么Length(s)就可以表示為： X_Map.coords X_map.Coords-1，算式只需求得Belong（s）即可。如圖6，可以看到在問題的離散化之后，一組橫向超元線段從上到下，數(shù)目是有限的，約有N*2條。這使得我們很容易想到線性結(jié)構(gòu)。例

12、如用一維數(shù)組來描述這么一組線段，用數(shù)組下標表示該線段從上到下的編號。數(shù)組雛形定義如下 VarA : array1.MaxSize of integer基于對一維數(shù)組的使用，可以得到一個稱為“累計掃描”的過程，來求解Belong(s)。累計掃描的思想是，將一維數(shù)組的元素看作計數(shù)器，計數(shù)器AI的內(nèi)容是覆蓋超元線段I的矩形上邊的數(shù)目 覆蓋超元線段I的矩形下邊的數(shù)目。形象表示如圖7： 圖7同時，設(shè)立累加器add，從上至下掃描超元線段，累加aI的值。由圖7中可以看出，一條超元線段I屬于輪廓的情況有兩種： 1、AI0且掃描到該超元線段未累加時add = 0（超元線段I是矩形上邊的情況） 2、AI0且掃描到

13、該超元線段累加之后add = 0（超元線段I是矩形下邊的情況） 這樣，對于一組超元線段求解Belong(s)可以分為兩部分： 1、對AI賦值，即累計過程。 2、從上至下掃描一組超元線段并累加add，即掃描過程。Belong(s)的值在掃描過程中得到。至此，描述一組超元線段狀態(tài)的數(shù)據(jù)結(jié)構(gòu)基本確立，存儲結(jié)構(gòu)是線性一維數(shù)組，定義的操作包括累計與掃描兩個部分。定義如下： TypeGroup_TYPE = Object A : array1.MaxSize of Integer; 線性地記錄一組超元線段的信息，如圖7 Procedure Count; 累計的過程 Function Adding; 掃描的

14、過程，即求解Belong(s)的過程EndProcedure Group_TYPE.Count 累計的過程1 數(shù)組A清零2 for I ß 1 to N3 do if 矩形I跨越了超元線段組S 即矩形的左右邊分別在線段兩側(cè)4 then A矩形I的上邊 ß A矩形I的上邊 + 15 A矩形I的下邊 ß A矩形I的下邊 - 1所謂“矩形I的上邊”指矩形I上邊縱坐標的映射編號，“矩形I的下邊”同F(xiàn)unction Group_TYPE.Adding 掃描的過程，函數(shù)值即為Belong(S)的值1 調(diào)用 Count2 add ß 03 sum ß 04

15、for I ß 1 to 縱坐標的最大映射編號5 do if aI 0 6 then if add = 0 7 then sum ß sum + 1 該線段是矩形的上邊8 add ß add + aI9 if add = 0 10 then sum ß sum + 1 該線段是矩形的下邊11 return sum Count與Adding用于一組超元線段的累計掃描 VarScan : Group_TYPE數(shù)據(jù)結(jié)構(gòu)確立后，Belong(s)通過調(diào)用Scan.Adding來計算，算式得以實現(xiàn)。以上的操作針對一維數(shù)組而設(shè)計，用于進行一組超元線段的累計掃描過程。

16、執(zhí)行Scan.Adding的時間復雜度為O(N)。橫向超元線段分為2*N-1組，固求解橫向輪廓周長的算法時間復雜度為O(N2)。同理，求解縱向輪廓周長的復雜度也為O(N2)，則Picture問題的算法時間復雜度為O(N2)。雖然這是一個多項式階，但在最壞情況下（N接近5000時）還有一定的計算量。對數(shù)據(jù)結(jié)構(gòu)選擇的進一步分析累計掃描過程體現(xiàn)了一種認識和思維方式，以一維數(shù)組作為數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，這里是否有更好的做法，我們將作進一步分析。 通過求解問題對數(shù)據(jù)結(jié)構(gòu)選擇作的分析中，我們注意到在選擇數(shù)據(jù)結(jié)構(gòu)需要考慮的幾個方面： 1、數(shù)據(jù)結(jié)構(gòu)要適應(yīng)問題的狀態(tài)描述。解決問題時需要對狀態(tài)進行描述，在程序中，要涉及到

17、狀態(tài)的存儲、轉(zhuǎn)換等。選擇的數(shù)據(jù)結(jié)構(gòu)必需先適用于描述狀態(tài)，并使對狀態(tài)的各種操作能夠明確地定義在數(shù)據(jù)結(jié)構(gòu)上。在Picture問題中，涉及到算法的狀態(tài)是關(guān)于一組“超元線段”的描述，目的是要確定該組超元線段的數(shù)目，我們選擇了線性結(jié)構(gòu)，采用計數(shù)掃描的方法，統(tǒng)計超元線段屬于輪廓的數(shù)目。這種表示法直觀、易于實現(xiàn)，可以說基本適用于描述狀態(tài)。但采用一維數(shù)組，效率并不高，一次掃描耗時較大。其中主要的原因是各組超元線段的掃描分別獨立，后面的掃描并不能利用前面的結(jié)論。 2、數(shù)據(jù)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)。數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，其選擇要充分考慮算法的各種操作，同時數(shù)據(jù)結(jié)構(gòu)的選擇也影響著算法的設(shè)計。我們有這樣的認識和經(jīng)

18、歷，如果算法是對一個隊列進行堆排序，就應(yīng)當選擇能夠迅速定位的數(shù)據(jù)結(jié)構(gòu)，如一維數(shù)組等，而不應(yīng)選擇像鏈表這樣定位耗時的數(shù)據(jù)結(jié)構(gòu)，反之，如果要對一個鏈表進行排序，則基于鏈表結(jié)構(gòu)的基數(shù)排序應(yīng)當是首選對象。Picture問題的算法思想基于問題的離散化，需要對平面進行分割，記錄分割點的坐標。通常，使用映射來記錄分割點。采用數(shù)組形式，利用其下標與數(shù)組元素的自然對應(yīng)，實現(xiàn)映射，直截了當。這樣選擇基本可以滿足算法要求。同時，在選擇數(shù)據(jù)結(jié)構(gòu)時，也要考慮其對算法的影響。數(shù)據(jù)結(jié)構(gòu)對算法的影響主要在兩方面：u 數(shù)據(jù)結(jié)構(gòu)的存儲能力。如果數(shù)據(jù)結(jié)構(gòu)存儲能力強、存儲信息多，算法將會較好設(shè)計。反之對于過于簡單的數(shù)據(jù)結(jié)構(gòu)，可能就要

19、設(shè)計一套比較復雜的算法了。在這一點上，經(jīng)常體現(xiàn)時間與空間的矛盾，往往存儲能力是與所使用的空間大小成正比的。u 定義在數(shù)據(jù)結(jié)構(gòu)上的操作。“數(shù)據(jù)結(jié)構(gòu)”一詞之所以不同于“變量”，主要在于數(shù)據(jù)結(jié)構(gòu)上定義了基本操作，這些操作都有較強的實際意義。這些操作就好比工具，有了好的工具，算法設(shè)計也會比較輕松。Picture問題中選擇了線性結(jié)構(gòu)，它定義的操作比較簡單，因此無法很好地將不同組的超元線段統(tǒng)計聯(lián)系起來。 3、數(shù)據(jù)結(jié)構(gòu)的選擇同時要兼顧編程的方便。許多復雜的數(shù)據(jù)結(jié)構(gòu)能夠得到較好的效率，但編程復雜，不易實現(xiàn)且容易出錯。在這種情況下，如果能夠選擇一種我們較為熟悉的又不會過多地降低程序效率的數(shù)據(jù)結(jié)構(gòu)，倒不失為一種折

20、中的辦法。如Picture問題中的Group_TYPE.Count過程的4、5兩步，要求出某個矩形邊對應(yīng)的映射編號。我們定義的映射僅僅是編號à坐標值，并不是坐標值à編號。如果再實現(xiàn)這一映射，勢必增加編程難度。所以編程求精時，可以認為以整數(shù)而不是以頂點坐標對平面進行橫向切割。這樣映射關(guān)系很好建立，坐標值本身就是編號，減少了編程難度。如果進一步以頂點坐標作橫向切割，當然會提高程序效率，但效果并不明顯掃描計數(shù)仍需要O(N)的時間，這是很昂貴的，所以進一步切割并不影響算法主要部分的效率，另一方面，編程難度卻會大大提高，得不償失。由此看出，在算法效率“大局已定”的情況下，有時也需要適

21、當?shù)貭奚绦蛐蕘頊p少編程不必要的麻煩。 4、靈活應(yīng)用已有知識。我們對編程都積累了一定的經(jīng)驗，對以后的解題有很大幫助。一個“新問題”有時與“舊問題”有許多內(nèi)在的聯(lián)系，往往能夠?qū)⑿聠栴}轉(zhuǎn)化為所學過的知識，或者由所學過的知識得到啟發(fā)，從而解決問題。所謂“新”數(shù)據(jù)結(jié)構(gòu)的構(gòu)造，有時可以是幾種基本數(shù)據(jù)結(jié)構(gòu)的有機結(jié)合，或者由基本數(shù)據(jù)結(jié)構(gòu)得到啟發(fā)而得到。做到“溫故而知新”，是對算法設(shè)計者創(chuàng)新意識的要求。當然，對一個問題，要首先考慮現(xiàn)成的、經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。如隊列、棧、鏈表等等，其標準結(jié)構(gòu)與標準運算已經(jīng)有了“公論”，程序?qū)崿F(xiàn)也經(jīng)過了“千錘百煉”，效率已經(jīng)很完美。如果找到一種可行的經(jīng)典數(shù)據(jù)結(jié)構(gòu)，那么算法實現(xiàn)一般來

22、說就比較輕松。要做到這一點，要求我們有扎實的基礎(chǔ)知識，對各種算法及數(shù)據(jù)結(jié)構(gòu)了然于胸。在計數(shù)掃描過程中采用了經(jīng)典的線性一維數(shù)組，是一個很自然的考慮方向，并且可以很容易上機實現(xiàn)，不足之處在于其效率較低?？偟貋碚f，Picture問題算法思想的方向還是基本正確的。Picture問題最大數(shù)據(jù)應(yīng)包含近5000個矩形，這樣大的數(shù)據(jù)量決定了要降低規(guī)模是“大勢所趨”，所以對問題的離散化處理是合理的選擇。至于效率不高，應(yīng)當是線性數(shù)據(jù)結(jié)構(gòu)的選擇造成的。由此，我們可以看到使用線性結(jié)構(gòu)來實現(xiàn)Picture問題還有一些缺陷，其中最主要的是各組超元線段的統(tǒng)計相互獨立，聯(lián)系不緊，這是算法效率不高的“瓶頸”。為了解決這個問題，

23、我們嘗試用其它的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)算法，像前面一樣，這個數(shù)據(jù)結(jié)構(gòu)應(yīng)該符合以下的條件： 1、同線性結(jié)構(gòu)一樣，新數(shù)據(jù)結(jié)構(gòu)要適用于描述一組超元線段的狀態(tài)。至少，新結(jié)構(gòu)要合理地表示一組超元線段屬于輪廓的部分，或者說它要能準確地且較快地計算出算式中Belong(s)的值。 2、新結(jié)構(gòu)也要與基本算法相適應(yīng)。新結(jié)構(gòu)仍然以問題的離散化為基礎(chǔ)，映射結(jié)構(gòu)應(yīng)當保留事實上映射結(jié)構(gòu)在時間效率上并沒有缺點。新結(jié)構(gòu)在描述超元線段組時則要設(shè)法將不同組超元線段的統(tǒng)計有機結(jié)合起來。 3、新結(jié)構(gòu)還要兼顧編程的方便。如果選擇的數(shù)據(jù)結(jié)構(gòu)編程難度太大，以至于無法上機實現(xiàn)，或者只是理論上的“高效率”，對解題沒有實際意義。這么說也許太夸張，但實

24、際上也常常存在“魚與熊掌不可兼得”的情況。大部分高級數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)都需要一定的編程技巧。就像問題在時間效率與空間效率上的矛盾一樣，算法效率與編程難度也有矛盾，一般來說算法效率越高，編程難度也會越大?？紤]新結(jié)構(gòu)時希望能找到實現(xiàn)較為容易的數(shù)據(jù)結(jié)構(gòu)。綜合以上分析，由于線性結(jié)構(gòu)并不能給我們帶來令人滿意的效率，所以我們嘗試用樹形結(jié)構(gòu)來描述一組超元線段的狀態(tài)，實現(xiàn)Picture問題的基本算法。為了提高效率，采用的樹結(jié)構(gòu)必需是平衡樹，我們姑且稱之為“超元線段樹”。Picture問題的深入討論基于對數(shù)據(jù)結(jié)構(gòu)選擇的進一步分析，我們來重新考慮一下Picture問題的數(shù)據(jù)結(jié)構(gòu)的選擇，即采用樹形結(jié)構(gòu)來描述一組超元線段

25、的狀態(tài)。一、 線段樹受到累計掃描過程的啟發(fā)，一組超元線段屬于輪廓的數(shù)目，它與跨越該組超元線段的矩形的縱向邊位置關(guān)系密切。不妨把矩形的縱向邊投影到Y(jié)軸上，這樣就把矩形的縱向邊看作閉區(qū)間，并稱之為閉區(qū)間Q。我們以“線段樹”的樹形數(shù)據(jù)結(jié)構(gòu)來描述閉區(qū)間Q。作為工具，先簡單研究線段樹的特點。線段樹是描述單個或若干區(qū)間并的樹形結(jié)構(gòu)，屬于平衡樹的一種。使用線段樹要求知道所描述的區(qū)間端點可能取到的值。換句話說，設(shè)A1.N是從小到大排列的區(qū)間端點集合，對于任意一個待描述的閉區(qū)間P=x,y，存在1ijN使得x=ai且y=aj，這里i, j稱為x,y的編號。可以看到，即使是實數(shù)坐標，在線段樹中也只有整數(shù)含義。以下所

26、說的區(qū)間x, y如無特殊說明，x、y均是整數(shù)，即原始區(qū)間頂點坐標的編號。線段樹是一棵二叉樹，將數(shù)軸劃分成一系列的初等區(qū)間I, I+1 (I=1N-1)。每個初等區(qū)間對應(yīng)于線段樹的一個葉結(jié)點。線段樹的內(nèi)部結(jié)點對應(yīng)于形如 I, J (J I > 1)的一般區(qū)間。一般情況下，線段樹的結(jié)點類型定義如下： TypeLines_Tree = Object i, j : integer; 結(jié)點表示的區(qū)間的頂點標號I, J count : integer; 覆蓋這一結(jié)點的區(qū)間數(shù) leftchild, rightchild : Lines_Tree; 二叉樹的兩個子結(jié)點end關(guān)于Lines_Tree的其它

27、數(shù)據(jù)域與定義的運算將陸續(xù)添加。圖8是一棵線段樹，描述的區(qū)間端點可以有10種取值。其中記錄著一個區(qū)間3，6，它用紅色的3，5及5，6的并采表示。圖中紅色結(jié)點的count域值為1，黑色結(jié)點的count域值為0。圖8直觀地看，子結(jié)點就是父結(jié)點區(qū)間平均分成兩部分。設(shè)L, R是父結(jié)點的區(qū)間端點，我們可以增加Lines_Tree.Build(l, r : integer)遞歸地定義線段樹如下:Procedure Lines_tree.Build(l, r : integer)1 I ß l 左端點2 J ß r 右端點3 Count ß 0 初始化4 If r - l >

28、; 1 是否需要生成子結(jié)點，若r-l=1則是初等區(qū)間5 then k ß (l + r) 平均分為兩部分6 new(leftchild)7 leftchild.Build(l, k) 建立左子樹8 new(rightchild)9 rightchild.Build(k, r) 建立右子樹10 else leftchild ß nil11 rightchild ß nil設(shè)根結(jié)點是Root，建樹需要執(zhí)行Root.Build。由遞歸定義看出，線段樹是一棵平衡樹，高度為logN。建立整棵樹需要的時間為O(N)。以上著重說明了線段樹的存儲原理，我們還應(yīng)建立線段樹的基本運算

29、。線段樹可以存儲多個區(qū)間，所以支持區(qū)間插入運算Lines_Tree.Insert(l, r : integer)，定義如下：Procedure Lines_Tree.Insert(l, r : integer) l, r是待插入?yún)^(qū)間，l、r都是原始頂點坐標1 if (l <= ai) and (aj <= r) 2 then count ß count + 1 蓋滿整個結(jié)點區(qū)間3 else if l < a(i + j) div 2 是否能覆蓋到左孩子結(jié)點區(qū)間4 then leftchild.Insert(l, r) 向左孩子插入5 if r > a(i +

30、j) div 2 是否能覆蓋到右孩子結(jié)點區(qū)間6 then rightchild.Insert(l, r) 向右孩子插入類似地，線段樹支持區(qū)間的刪除Lines_Tree.Delete(l, r : integer)，定義如下：Procedure Lines_Tree.Delete(l, r : integer) l, r是待刪除區(qū)間，l、r都是原始頂點坐標1 if (l <= ai) and (aj <= r) 2 then count ß count - 1 蓋滿整個結(jié)點區(qū)間3 else if l < a(i + j) div 2 是否能覆蓋到左孩子結(jié)點區(qū)間4 th

31、en leftchild.Delete(l, r) 向左孩子刪除5 if r > a(i + j) div 2 是否能覆蓋到右孩子結(jié)點區(qū)間6 then rightchild.Delete(l, r) 向右孩子刪除執(zhí)行Lines_Tree.Delete(l, r : integer) 的先決條件是區(qū)間l, r曾被插入且還未刪除。如果建樹后插入?yún)^(qū)間2，5而刪除區(qū)間3，4是非法的。通過分析插入與刪除的路徑，可知Lines_Tree.Insert與Lines_Tree.Delete的時間復雜度均為O(logN)。(詳見附錄1)由于線段樹給每一個區(qū)間都分配了結(jié)點，利用線段樹可以求區(qū)間并后的測度與區(qū)

32、間并后的連續(xù)段數(shù)。(一)、 測度由于線段樹結(jié)構(gòu)遞歸定義，其測度也可以遞歸定義。增加數(shù)據(jù)域Lines_Tree.M表示以該結(jié)點為根的子樹的測度。M取值如下： aj ai 該結(jié)點Count>0M = 0 該結(jié)點為葉結(jié)點且Count=0 Leftchild.M + Rightchild.M 該結(jié)點為內(nèi)部結(jié)點且Count=0據(jù)此，可以用Lines_Tree.UpData來動態(tài)地維護Lines_Tree.M。UpData在每一次執(zhí)行Insert或Delete之后執(zhí)行。定義如下：Procedure Lines_Tree.UpData1 if count > 0 2 then M ß

33、aj i 蓋滿區(qū)間，測度為aj ai3 else if j - i = 1 是否葉結(jié)點4 then M ß 0 該結(jié)點是葉結(jié)點5 else M ß Leftchild.M + Rightchild.M 內(nèi)部結(jié)點UpData的復雜度為O(1)，則用UpData來動態(tài)維護測度后執(zhí)行根結(jié)點的Insert與Delete的復雜度仍為O(logN)。(二)、 連續(xù)段數(shù)這里的連續(xù)段數(shù)指的是區(qū)間的并可以分解為多少個獨立的區(qū)間。如1，22，35，6可以分解為兩個區(qū)間1，3與5，6，則連續(xù)段數(shù)為2。增加一個數(shù)據(jù)域Lines_Tree.line表示該結(jié)點的連續(xù)段數(shù)。Line的討論比較復雜，內(nèi)部結(jié)

34、點不能簡單地將左右孩子的Line相加。所以再增加Lines_Tree.lbd與Lines_Tree.rbd域。定義如下： 1 左端點I被描述區(qū)間蓋到lbd = 0 左端點I不被描述區(qū)間蓋到 1 右端點J被描述區(qū)間蓋到rbd = 0 右端點J不被描述區(qū)間蓋到lbd與rbd的實現(xiàn)： 1 該結(jié)點count > 0lbd = 0 該結(jié)點是葉結(jié)點且count = 0 leftchild.lbd 該結(jié)點是內(nèi)部結(jié)點且Count=0 1 該結(jié)點count > 0rbd = 0 該結(jié)點是葉結(jié)點且count = 0 rightchild.rbd 該結(jié)點是內(nèi)部結(jié)點且Count=0有了lbd與rbd，Li

35、ne域就可以定義了： 1 該結(jié)點count > 0Line = 0 該結(jié)點是葉結(jié)點且count = 0 Leftchild.Line + Rightchild.Line - 1 當該結(jié)點是內(nèi)部結(jié)點且Count=0，Leftchild.rbd = 1且Rightchild.lbd = 1 Leftchild.Line + Rightchild.Line 當該結(jié)點是內(nèi)部結(jié)點且Count=0，Leftchild.rbd與Rightchild.lbd不都為1據(jù)此，可以定義UpData動態(tài)地維護Line域。與UpData相似，UpData也在每一次執(zhí)行Insert或Delete后執(zhí)行。定義如下：P

36、rocedure Lines_Tree.UpData1 if count > 0 是否蓋滿結(jié)點表示的區(qū)間2 then lbd ß 13 rbd ß 14 Line ß 15 else if j - i = 1 是否為葉結(jié)點6 then lbd ß 0 進行到這一步，如果為葉結(jié)點， count = 07 rbd ß 08 line ß 09 else line ß Leftchild.line + Rightchild.line - Leftchild.rbd * Rightchild.lbd 用乘法確定Leftchil

37、d.rbd與Rightchild.lbd是否同時為1同時，由于增加了Line、M等幾個數(shù)據(jù)域，在建樹Lines_Tree.Build時要將新增的域初始化。至此，線段樹構(gòu)造完畢，完整的線段樹定義如下：Lines_Tree = object i, j : integer; count : integer; line : integer; lbd, rbd : byte; m : integer; leftchild, rightchild : Lines_tree; procedure Build(l, r : integer); procedure Insert(l, r : integer);

38、 procedure Delete(l, r : integer); procedure UpData; procedure UpData;end有了線段樹這個工具，可以考慮利用樹形結(jié)構(gòu)來描述一組超元線段的狀態(tài)。二、 Picture問題的數(shù)據(jù)結(jié)構(gòu)選擇之二：樹形結(jié)構(gòu)采用線性結(jié)構(gòu)描述一組超元線段的狀態(tài)并不能帶來太高的效率，其中主要原因是各組超元線段聯(lián)系不緊。如圖9所示，超元線段CD與EF被矩形AGHB遮蓋，不屬于輪廓；而與之相鄰DD與FF則“擺脫”了矩形的遮蓋，屬于輪廓的一部分。 圖9 圖10由此類推，可以看出相鄰的超元線段組都有類似的問題。如圖9，DD與FF不被遮蓋，可以這樣分析：從左往右，CD

39、、EF首先被遮蓋，但隨著BF的出現(xiàn)，對DD、FF的遮蓋自然消失。這一點，正是相鄰超元線段組的內(nèi)在聯(lián)系。用線性結(jié)構(gòu)無法表示出這一聯(lián)系，因為各組的累計掃描過程是獨立的。現(xiàn)在我們用樹形結(jié)構(gòu)來表示將較好地解決這一問題，因為線段樹支持插入與刪除及動態(tài)維護，可以有機聯(lián)系各組超元線段的狀態(tài)。我們把“從左往右”當作一個掃描的過程，若將其嚴格地描述，可以得到一個稱為線段掃描的過程：1. 設(shè)立掃描線段L。2. L從左往右掃描，停留在每一超元線段組上。如圖10所示。3. L的狀態(tài)用線段樹來表示，每一條縱向的矩形邊看作一個待合并區(qū)間。線段樹的連續(xù)段數(shù)*2表示該組超元線段屬于輪廓的線段數(shù)目。如圖10，L的狀態(tài)首先是G,

40、AE,C，連續(xù)線段數(shù)是1，所以1*2=2是該組超元線段屬于輪廓的數(shù)目。接著L進一步掃描，狀態(tài)改變?yōu)镋,C, 連續(xù)線段數(shù)是1，所以該組超元線段屬于輪廓的數(shù)目也是1*2=2。這樣，上文所說的“超元線段樹”就用線段樹來實現(xiàn)。為了統(tǒng)一起見，以后仍稱線段樹。4. 掃描過程中動態(tài)地維護L的狀態(tài)。參看圖10，L狀態(tài)的轉(zhuǎn)換是在線段樹中刪去區(qū)間H,B即G,A造成的。歸納一下，有以下結(jié)論：u L初始化為空，即線段樹剛建好時的情形。u 掃描時，遇到矩形左邊，將其插入（Insert）線段樹。u 掃描時，遇到矩形右邊，將其從線段樹中刪除（Delete）。由于從左往右掃描，事先插入了該矩形的左邊，所以刪除合法。參看算式，

41、以上的線段掃描過程可以得到每一組超元線段的Belong(s)，進一步得到整個圖形輪廓的橫向邊長。同時，線段掃描過程還可以在一次從左到右的掃描中求得圖形輪廓的縱向邊長。還以圖10為例。在掃描線狀態(tài)改變之前，L是G,AE,C；改變狀態(tài)之后，H,F、D,B就“露”了出來，成為輪廓一部分。G,AE,C正是L改變前后測度的差。如果描述相鄰的掃描線狀態(tài)的線段樹分別為Tree1、Tree2，則掃描過程中“露出”的縱向邊長度為|Tree1.M Tree2.M|。在掃描過程中，遇到的插入或刪除稱為“事件”，待插入或刪除的線段稱為“事件線段”。在掃描之前，應(yīng)將事件按橫坐標從小到大排序。（詳見附錄2）通過以上分析，

42、得到較之線性結(jié)構(gòu)的累計掃描過程改進的線段掃描過程的算法：1. 以矩形頂點坐標切割平面，實現(xiàn)橫縱坐標的離散化并建立映射X_Map、Y_Map。2. 事件排序3. Root.Build(1, N*2)4. Nowm ß 05. NowLine ß 06. Ans ß 07. for I ß 1 to 事件的最大編號8. do if I是插入事件 9. then Root.Insert(Y_Map.Coord事件線段頂點1， Y_Map.Coord事件線段頂點2)10. else Root.Delete(Y_Map.Coord事件線段頂點1， Y_Map.Coord事件線段頂點2)11. nowM ß Root.M12. nowLine ß Root.Line13. ans ß ans + l