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

數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率——從IOI98試題PICTURE談起-PAGE52- IOI’99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選IOI’99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選 -PAGE51-IOI’99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選 -PAGE21-數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率——從IOI98試題PICTURE談起【關(guān)鍵字】數(shù)據(jù)結(jié)構(gòu)的的選擇線線性結(jié)構(gòu)構(gòu)樹(shù)形結(jié)結(jié)構(gòu)【摘要】算法+數(shù)據(jù)結(jié)結(jié)構(gòu)=程序。設(shè)設(shè)計(jì)算法法與選擇擇合適的的數(shù)據(jù)結(jié)結(jié)構(gòu)是程程序設(shè)計(jì)計(jì)中相輔輔相成的的兩方面面，缺一一不可。數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇一直是是程序設(shè)設(shè)計(jì)中的的重點(diǎn)、難難點(diǎn)，正正確地應(yīng)應(yīng)用數(shù)據(jù)據(jù)結(jié)構(gòu)，往往往能帶帶來(lái)意想想不到的的效果。反反之，如如果忽視視了數(shù)據(jù)據(jù)結(jié)構(gòu)的的重要性性，對(duì)某某些問(wèn)題題有時(shí)就就得不到到滿意的的解答。通通過(guò)對(duì)IIOI998試題題Piccturre的深深入討論論，我們們可以看看到兩種種不同的的數(shù)據(jù)結(jié)結(jié)構(gòu)在解解題中的的應(yīng)用，以以及由此此得到的的不同的的算法效效率。本本文以PPictturee問(wèn)題為為例，探探討數(shù)據(jù)據(jù)結(jié)構(gòu)的的選擇對(duì)對(duì)算法效效率的影影響。【正文】引言算法通常是是決定程程序效率率的關(guān)鍵鍵，但一一切算法法最終都都要在相相應(yīng)的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)上實(shí)現(xiàn)現(xiàn)，許多多算法的的精髓就就是在于于選擇了了合適的的數(shù)據(jù)結(jié)結(jié)構(gòu)作為為基礎(chǔ)。在在程序設(shè)設(shè)計(jì)中，不不但要注注重算法法設(shè)計(jì)，也也要正確確地選擇擇數(shù)據(jù)結(jié)結(jié)構(gòu)，這這樣往往往能夠事事半功倍倍。在算法時(shí)間間與空間間效率的的兩方面面，著重重分析時(shí)時(shí)間效率率，即算算法的時(shí)時(shí)間復(fù)雜雜度，因因?yàn)槲覀儌兛偸窍ＯＭ绦蛐蛟谳^短短的時(shí)間間內(nèi)給出出我們所所希望的的輸出。如如果在空空間上過(guò)過(guò)于“吝吝嗇”而而使得時(shí)時(shí)間上無(wú)無(wú)法承受受，對(duì)解解題并無(wú)無(wú)益處。本文對(duì)IOOI988的試題題Piccturre作一一些分析析，通過(guò)過(guò)兩種不不同數(shù)據(jù)據(jù)結(jié)構(gòu)的的選擇，將將了解到到數(shù)據(jù)結(jié)結(jié)構(gòu)對(duì)算算法本身身及算法法效率的的影響。Pictuure問(wèn)問(wèn)題及算算法設(shè)計(jì)計(jì)Pictuure問(wèn)問(wèn)題Pictuure問(wèn)問(wèn)題是IIOI998的一一道試題題，描述述如下：：墻上貼著一一些海報(bào)報(bào)、照片片等矩形形，所有有的邊都都為垂直直或水平平。每個(gè)個(gè)矩形可可以被其其它矩形形部分或或完全遮遮蓋，所所有矩形形合并成成區(qū)域的的邊界周周長(zhǎng)稱為為輪廓周周長(zhǎng)。例如圖1的的三個(gè)矩矩形輪廓廓周長(zhǎng)為為30：圖1要求編寫(xiě)程程序計(jì)算算輪廓周周長(zhǎng)。數(shù)據(jù)量限制制：0≤矩形數(shù)數(shù)目<50000；坐標(biāo)數(shù)值為為整數(shù)，范范圍是[[-1000000，100000]]。算法描述在算法的大大體描述述中，將將不涉及及到具體體的數(shù)據(jù)據(jù)結(jié)構(gòu)，便便于數(shù)據(jù)據(jù)結(jié)構(gòu)的的進(jìn)一步步選擇和和比較分分析。、輪廓的定定義在描述算法法前，我我們先明明確一下下“輪廓廓”的定定義：1、輪廓由由有限條條線段組組成，線線段是矩矩形邊或或者矩形形邊的一一部分。2、組成矩矩形邊的的線段不不應(yīng)被任任何矩形形遮蓋。圖圖2與圖3分別是是遮蓋的的兩種情情況。圖2圖3圖圖4（AB被遮遮蓋）（CD被遮遮蓋）、元線段本題的一大大特征是是分析矩矩形的邊邊，而邊邊的端點(diǎn)點(diǎn)（即矩矩形的頂頂點(diǎn)）坐坐標(biāo)為整整數(shù)，且且坐標(biāo)取取值范圍圍已經(jīng)限限定在[[-1000000，100000]]之間。這這樣，就就可以把把這個(gè)平平面理解解成為一一個(gè)網(wǎng)格格。由于于給出的的坐標(biāo)是是整數(shù)，所所以矩形形邊一定定在網(wǎng)格格線上。在在網(wǎng)格中中，對(duì)于于一條線線段我們們最關(guān)心心其絕對(duì)對(duì)坐標(biāo)。如如圖4，我我們認(rèn)為為矩形邊邊AB由線線段L1、L2、L3組成。像像L1、L2、L3這樣連連接相鄰鄰網(wǎng)格頂頂點(diǎn)的基基本線段段，稱之之為“元元線段”，這這樣就把把矩形邊邊離散化化了。顯顯然，有有限的元元線段覆覆蓋了所所有的網(wǎng)網(wǎng)格線，且且元線段段是組成成矩形邊邊乃至組組成輪廓廓的基本本單位。一一條元線線段要么么完全屬屬于輪廓廓，要么么完全不不屬于輪輪廓。這這種定義義使我們們對(duì)問(wèn)題題的研究究具體到到每一條條元線段段，這樣樣的離散散化處理理有利于于問(wèn)題的的進(jìn)一步步討論。、超元線段段元線段的引引入，使使問(wèn)題更更加具體體。但也也應(yīng)當(dāng)看看到，平平面中共共有2000011*2000000*2條條元線段段，研究究的對(duì)象象過(guò)多，而而且計(jì)算算量受到到網(wǎng)格大大小的影影響，如如果頂點(diǎn)點(diǎn)坐標(biāo)范范圍是[[-1,,0000,0000，1,0000,0000]，元元線段數(shù)數(shù)目將達(dá)達(dá)到8**10^^12，這是是天文數(shù)數(shù)字。因因此有必必要對(duì)“元元線段”進(jìn)進(jìn)行優(yōu)化化。受到到元線段段的啟發(fā)發(fā)，我們們定義一一種改進(jìn)進(jìn)后的元元線段———“超超元線段段”，它它將由對(duì)對(duì)平面的的“切割割”得到到。具體體做法是是，根據(jù)據(jù)每個(gè)矩矩形縱向向邊的橫橫坐標(biāo)縱縱向地對(duì)對(duì)平面進(jìn)進(jìn)行2**N次切割割、根據(jù)據(jù)矩形橫橫向邊的的縱坐標(biāo)標(biāo)橫向地地對(duì)矩形形進(jìn)行22*N次切割割（N為矩形形個(gè)數(shù)）。顯顯然，經(jīng)經(jīng)過(guò)切割割后的平平面被分分成了((2*N++1)^^2個(gè)區(qū)區(qū)域，如如圖5所示：：圖圖5圖圖6其中像橫向向邊ABB、縱向向邊CDD這樣的的線段就就是“超超元線段段”。超超元線段段與元線線段有著著相似的的性質(zhì)，也也是組成成輪廓的的基本單單位。所所不同的的是，超超元線段段的數(shù)目目較少，一一般為44*N條左左右，且且超元線線段數(shù)目目不受網(wǎng)網(wǎng)格大小小的影響響。基于超元線線段的優(yōu)優(yōu)點(diǎn)，算算法最終終將研究究超元線線段。離散化及算算法框架架算法的研究究對(duì)象是是超元線線段，但但這并不不等于逐逐一枚舉舉，那樣樣耗時(shí)過(guò)過(guò)大，而而整體考考慮又使使得問(wèn)題題無(wú)從下下手。有有一種考考慮方法法是折中中的，即即既不研研究每一一條超元元線段，也也不同時(shí)時(shí)研究所所有的超超元線段段，而是是再進(jìn)一一步優(yōu)化化問(wèn)題的的離散化化，即將超元元線段分分組研究究。如圖圖6所示，夾夾在兩條條縱向分分割邊的的超元線線段自然然地分為為一組，它它們的共共同點(diǎn)是是長(zhǎng)度相相同，并并且端點(diǎn)點(diǎn)的橫坐坐標(biāo)相同同?？v向向線段也也可以進(jìn)進(jìn)行類似似的離散散化。這樣的離散散化處理理后，使使得問(wèn)題題規(guī)模降降低，以以此為基基礎(chǔ)，算算法的框框架可以以基本確確定為：：11、對(duì)平平面進(jìn)行行分割。22、累加加器anns0。33、研究究每組超超元線段段，檢測(cè)測(cè)其中屬屬于輪廓廓的部分分的長(zhǎng)度度，并把把這一長(zhǎng)長(zhǎng)度累加加入anns。44、輸出出anss的值。以上只是算算法的基基本框架架，還很很粗糙，求求精部分分有賴于于數(shù)據(jù)結(jié)結(jié)構(gòu)的具具體選擇擇。Pictuure問(wèn)問(wèn)題的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)選擇之之一：線線性結(jié)構(gòu)構(gòu)映射結(jié)構(gòu)的的建立算法的基礎(chǔ)礎(chǔ)是問(wèn)題題的離散散化，要要進(jìn)行平平面“分分割”，一一般需要要記錄分分割點(diǎn)，通常采用映射來(lái)記錄分割點(diǎn)。直觀的做法是采用一維數(shù)組形式，下標(biāo)表示分割點(diǎn)的編號(hào)，數(shù)組元素表示分割點(diǎn)的坐標(biāo)。利用下標(biāo)與數(shù)組元素的自然對(duì)應(yīng)，實(shí)現(xiàn)映射。應(yīng)該說(shuō)，這樣表示是比較自然的，實(shí)現(xiàn)也比較方便。數(shù)組的優(yōu)點(diǎn)主要是存取方便，且可以在O(NlogN)時(shí)間內(nèi)排序。映射結(jié)構(gòu)定義如下：TyppeMappeed_TTYPEE=ObjjecttLeen::0...Maax;{記記下分割割點(diǎn)的個(gè)個(gè)數(shù)}Cooordd:aarraay[11..MMax]]offinntegger;;{記記下分割割點(diǎn)坐標(biāo)標(biāo)}PrroceedurreCreeat;;{{映射初初始化}}PrroceedurreInnserrt(XX:inttegeer);;{插插入分割割坐標(biāo)XX}PrroceedurreSoort;;{對(duì)坐坐標(biāo)排序序}End以下是三個(gè)個(gè)過(guò)程的的描述與與解釋：：ProceedurreMapppedd_TYYPE..CreeatLen0{Creaat用用于初始始化該映映射}ProceedurreMapppedd_TYYPE..Inssertt(X:IInteegerr)LenLenn+1Coordd[Leen]X{Inseert用于插插入一個(gè)個(gè)分割坐坐標(biāo)，此此時(shí)坐標(biāo)標(biāo)之間是是無(wú)序的的}ProceedurreMapppedd_TYYPE..Sorrt略{Sortt用于于將Leen個(gè)坐坐標(biāo)排序序。由于于Cooord是是一維數(shù)數(shù)組，SSortt容易實(shí)實(shí)現(xiàn)，例例如快速速排序。設(shè)設(shè)N=Lenn，Sorrt效率可可達(dá)O((NloogN))。針對(duì)對(duì)整數(shù)，也也可以采采用筒排排序得到到更好的的效率，但但這不是是問(wèn)題的的關(guān)鍵部部分。}}VarrX_mapp,Y_mmap:Maappeed_TTYPEE{分分別記錄錄橫縱坐坐標(biāo)的映映射}以橫坐標(biāo)為為例，在在程序處處理時(shí)，首首先執(zhí)行行X_mmap..Creeat初初始化映映射。而而后通過(guò)過(guò)X_mmap..Inssertt將每個(gè)個(gè)矩形縱縱向邊的的橫坐標(biāo)標(biāo)作為分分割坐標(biāo)標(biāo)插入XX_maap.CCoorrd，最最后執(zhí)行行X_mmap..Sorrt進(jìn)行行排序。至此，映射射建立完完畢。應(yīng)該說(shuō)，這這一部分分完全可可以滿足足算法要要求，且且執(zhí)行效效率較高高。三個(gè)個(gè)過(guò)程中中的Crreatt與Inssertt耗時(shí)均均為O((1)，Sorrt耗時(shí)時(shí)為O((NloogN))，但它它只需執(zhí)執(zhí)行一次次。線性結(jié)構(gòu)的的建立映射建立后后，相當(dāng)當(dāng)于完成成了對(duì)平平面的切切割?，F(xiàn)現(xiàn)在的主主要問(wèn)題題是如何何描述一一組超元元線段的的狀態(tài)。由由于最終終要計(jì)算算輪廓周周長(zhǎng)，我我們最關(guān)關(guān)心的是是一組超超元線段段中究竟竟有多少少條屬于于輪廓。由由分組的的方法可可知，每每組超元元線段長(zhǎng)長(zhǎng)度相同同。以下下均以橫橫向超元元線段為為例進(jìn)行行說(shuō)明。設(shè)設(shè)：超元線段組組編號(hào)11——N**2-11(N是是矩形數(shù)數(shù)目)編號(hào)為S的的超元線線段組中中的線段段長(zhǎng)度為為L(zhǎng)enngthh(S))編號(hào)為S的的超元線線段組中中屬于圖圖形輪廓廓的超元元線段數(shù)數(shù)目為BBeloong((S)算式①輪廓橫向邊周長(zhǎng)ANS=則：算式①輪廓橫向邊周長(zhǎng)ANS=其中Lennth((s)容容易求得得。如果果超元線線段組編編號(hào)以網(wǎng)網(wǎng)格中從從左到右右為原則則，那么么Lenngthh(s))就可以以表示為為：XX_Maap.ccoorrd[ss]––X__mapp.Cooordd[s--1]，算式式①只需求求得Beelonng（s）即可可。如圖6，可可以看到到在問(wèn)題題的離散散化之后后，一組組橫向超超元線段段從上到到下，數(shù)數(shù)目是有有限的，約約有N**2條。這這使得我我們很容容易想到到線性結(jié)結(jié)構(gòu)。例例如用一一維數(shù)組組來(lái)描述述這么一一組線段段，用數(shù)數(shù)組下標(biāo)標(biāo)表示該該線段從從上到下下的編號(hào)號(hào)。數(shù)組組雛形定定義如下下VarrA:aarraay[11..MMaxSSizee]oofiinteegerr基于對(duì)一維維數(shù)組的的使用，可可以得到到一個(gè)稱稱為“累累計(jì)掃描描”的過(guò)過(guò)程，來(lái)來(lái)求解BBeloong((s)。累累計(jì)掃描描的思想想是，將將一維數(shù)數(shù)組的元元素看作作計(jì)數(shù)器器，計(jì)數(shù)數(shù)器A[[I]的的內(nèi)容是是覆蓋超超元線段段I的矩形形上邊的的數(shù)目—覆蓋超超元線段段I的矩形形下邊的的數(shù)目。形形象表示示如圖77：圖7同時(shí)，設(shè)立立累加器器addd，從上上至下掃掃描超元元線段，累累加a[[I]的的值。由由圖7中可以以看出，一一條超元元線段II屬于輪輪廓的情情況有兩兩種：1、A[II]≠0且掃描描到該超超元線段段未累加加時(shí)addd==0（超超元線段段I是矩形形上邊的的情況）2、A[II]≠0且掃描描到該超超元線段段累加之之后addd==0（超超元線段段I是矩形形下邊的的情況）這樣樣，對(duì)于于一組超超元線段段求解BBeloong((s)可可以分為為兩部分分：1、對(duì)對(duì)A[II]賦值值，即累累計(jì)過(guò)程程。2、從從上至下下掃描一一組超元元線段并并累加aadd，即即掃描過(guò)過(guò)程。Belonng(ss)的值值在掃描描過(guò)程中中得到。至此，描述述一組超超元線段段狀態(tài)的的數(shù)據(jù)結(jié)結(jié)構(gòu)基本本確立，存存儲(chǔ)結(jié)構(gòu)構(gòu)是線性性一維數(shù)數(shù)組，定定義的操操作包括括累計(jì)與與掃描兩兩個(gè)部分分。定義義如下：：TyppeGroupp_TYYPE=OObjeectA:arrray[[1...MaxxSizze]ofInttegeer;{線性性地記錄錄一組超超元線段段的信息息，如圖圖7}ProoceddureeCCounnt;{累計(jì)計(jì)的過(guò)程程}FunnctiionAdddinng;{掃描描的過(guò)程程，即求求解Beelonng(ss)的過(guò)過(guò)程}EndProceedurreGrooup__TYPPE.CCounnt{累計(jì)的的過(guò)程}}數(shù)組A清零零forI11ttoNdoiff矩矩形I跨越了了超元線線段組SS{{即矩形形的左右右邊分別別在線段段兩側(cè)}}theenA[矩矩形I的上邊邊]A[[矩形I的上邊邊]++11AA[矩形形I的下邊邊]A[[矩形I的下邊邊]-11{所謂“矩矩形I的上邊邊”指矩矩形I上邊縱縱坐標(biāo)的的映射編編號(hào)，“矩矩形I的下邊邊”同}}FuncttionnGGrouup_TTYPEE.Adddinng{{掃描的的過(guò)程，函函數(shù)值即即為Beelonng(SS)的值值}調(diào)用Coounttadd00sum00forI11tto縱坐標(biāo)標(biāo)的最大大映射編編號(hào)doiffaa[I]]≠≠00theenifaddd=0theensummsuum+1{該線段段是矩形形的上邊邊}adddaddd+a[II]ifaddd=0theensuumssum+1{{該線段段是矩形形的下邊邊}returrnsumm{Counnt與Adddingg用于一一組超元元線段的的累計(jì)掃掃描}VarrScan:Grroupp_TYYPE數(shù)據(jù)結(jié)構(gòu)確確立后，Belong(s)通過(guò)調(diào)用Scan.Adding來(lái)計(jì)算，算式①得以實(shí)現(xiàn)。以上的操作作針對(duì)一一維數(shù)組組而設(shè)計(jì)計(jì)，用于于進(jìn)行一一組超元元線段的的累計(jì)掃掃描過(guò)程程。執(zhí)行行Scaan.AAddiing的的時(shí)間復(fù)復(fù)雜度為為O(NN)。橫橫向超元元線段分分為2**N-11組，固固求解橫橫向輪廓廓周長(zhǎng)的的算法時(shí)時(shí)間復(fù)雜雜度為OO(N^^2)。同同理，求求解縱向向輪廓周周長(zhǎng)的復(fù)復(fù)雜度也也為O((N^22)，則則Piccturre問(wèn)題題的算法法時(shí)間復(fù)復(fù)雜度為為O(NN^2))。雖然然這是一一個(gè)多項(xiàng)項(xiàng)式階，但但在最壞壞情況下下（N接近50000時(shí)時(shí)）還有有一定的的計(jì)算量量。對(duì)數(shù)據(jù)結(jié)構(gòu)構(gòu)選擇的的進(jìn)一步步分析累計(jì)掃描過(guò)過(guò)程體現(xiàn)現(xiàn)了一種種認(rèn)識(shí)和和思維方方式，以以一維數(shù)數(shù)組作為為數(shù)據(jù)結(jié)結(jié)構(gòu)基礎(chǔ)礎(chǔ)，這里里是否有有更好的的做法，我我們將作作進(jìn)一步步分析。通過(guò)求解解問(wèn)題對(duì)對(duì)數(shù)據(jù)結(jié)結(jié)構(gòu)選擇擇作的分分析中，我我們注意意到在選選擇數(shù)據(jù)據(jù)結(jié)構(gòu)需需要考慮慮的幾個(gè)個(gè)方面：：11、數(shù)據(jù)據(jù)結(jié)構(gòu)要要適應(yīng)問(wèn)問(wèn)題的狀狀態(tài)描述述。解決決問(wèn)題時(shí)時(shí)需要對(duì)對(duì)狀態(tài)進(jìn)進(jìn)行描述述，在程程序中，要要涉及到到狀態(tài)的的存儲(chǔ)、轉(zhuǎn)轉(zhuǎn)換等。選選擇的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)必需先先適用于于描述狀狀態(tài)，并并使對(duì)狀狀態(tài)的各各種操作作能夠明明確地定定義在數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)上。在在Piccturre問(wèn)題題中，涉涉及到算算法的狀狀態(tài)是關(guān)關(guān)于一組組“超元元線段”的的描述，目目的是要要確定該該組超元元線段的的數(shù)目，我我們選擇擇了線性性結(jié)構(gòu)，采采用計(jì)數(shù)數(shù)掃描的的方法，統(tǒng)統(tǒng)計(jì)超元元線段屬屬于輪廓廓的數(shù)目目。這種種表示法法直觀、易易于實(shí)現(xiàn)現(xiàn)，可以以說(shuō)基本本適用于于描述狀狀態(tài)。但但采用一一維數(shù)組組，效率率并不高高，一次次掃描耗耗時(shí)較大大。其中中主要的的原因是是各組超超元線段段的掃描描分別獨(dú)獨(dú)立，后后面的掃掃描并不不能利用用前面的的結(jié)論。22、數(shù)據(jù)據(jù)結(jié)構(gòu)應(yīng)應(yīng)與所選選擇的算算法相適適應(yīng)。數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)是為算算法服務(wù)務(wù)的，其其選擇要要充分考考慮算法法的各種種操作，同同時(shí)數(shù)據(jù)據(jù)結(jié)構(gòu)的的選擇也也影響著著算法的的設(shè)計(jì)。我我們有這這樣的認(rèn)認(rèn)識(shí)和經(jīng)經(jīng)歷，如如果算法法是對(duì)一一個(gè)隊(duì)列列進(jìn)行堆堆排序，就就應(yīng)當(dāng)選選擇能夠夠迅速定定位的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)，如一一維數(shù)組組等，而而不應(yīng)選選擇像鏈鏈表這樣樣定位耗耗時(shí)的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)，反之之，如果果要對(duì)一一個(gè)鏈表表進(jìn)行排排序，則則基于鏈鏈表結(jié)構(gòu)構(gòu)的基數(shù)數(shù)排序應(yīng)應(yīng)當(dāng)是首首選對(duì)象象。Piictuure問(wèn)問(wèn)題的算算法思想想基于問(wèn)問(wèn)題的離離散化，需需要對(duì)平平面進(jìn)行行分割，記記錄分割割點(diǎn)的坐坐標(biāo)。通通常，使使用映射射來(lái)記錄錄分割點(diǎn)點(diǎn)。采用用數(shù)組形形式，利利用其下下標(biāo)與數(shù)數(shù)組元素素的自然然對(duì)應(yīng)，實(shí)實(shí)現(xiàn)映射射，直截截了當(dāng)。這這樣選擇擇基本可可以滿足足算法要要求。同時(shí)，在選選擇數(shù)據(jù)據(jù)結(jié)構(gòu)時(shí)時(shí)，也要要考慮其其對(duì)算法法的影響響。數(shù)據(jù)據(jù)結(jié)構(gòu)對(duì)對(duì)算法的的影響主主要在兩兩方面：：數(shù)據(jù)結(jié)構(gòu)的的存儲(chǔ)能能力。如如果數(shù)據(jù)據(jù)結(jié)構(gòu)存存儲(chǔ)能力力強(qiáng)、存存儲(chǔ)信息息多，算算法將會(huì)會(huì)較好設(shè)設(shè)計(jì)。反反之對(duì)于于過(guò)于簡(jiǎn)簡(jiǎn)單的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)，可能能就要設(shè)設(shè)計(jì)一套套比較復(fù)復(fù)雜的算算法了。在在這一點(diǎn)點(diǎn)上，經(jīng)經(jīng)常體現(xiàn)現(xiàn)時(shí)間與與空間的的矛盾，往往往存儲(chǔ)儲(chǔ)能力是是與所使使用的空空間大小小成正比比的。定義在數(shù)據(jù)據(jù)結(jié)構(gòu)上上的操作作?！皵?shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)”一詞詞之所以以不同于于“變量量”，主主要在于于數(shù)據(jù)結(jié)結(jié)構(gòu)上定定義了基基本操作作，這些些操作都都有較強(qiáng)強(qiáng)的實(shí)際際意義。這這些操作作就好比比工具，有有了好的的工具，算算法設(shè)計(jì)計(jì)也會(huì)比比較輕松松。Piictuure問(wèn)問(wèn)題中選選擇了線線性結(jié)構(gòu)構(gòu)，它定定義的操操作比較較簡(jiǎn)單，因因此無(wú)法法很好地地將不同同組的超超元線段段統(tǒng)計(jì)聯(lián)聯(lián)系起來(lái)來(lái)。33、數(shù)據(jù)據(jù)結(jié)構(gòu)的的選擇同同時(shí)要兼兼顧編程程的方便便。許多多復(fù)雜的的數(shù)據(jù)結(jié)結(jié)構(gòu)能夠夠得到較較好的效效率，但但編程復(fù)復(fù)雜，不不易實(shí)現(xiàn)現(xiàn)且容易易出錯(cuò)。在在這種情情況下，如如果能夠夠選擇一一種我們們較為熟熟悉的又又不會(huì)過(guò)過(guò)多地降降低程序序效率的的數(shù)據(jù)結(jié)結(jié)構(gòu)，倒倒不失為為一種折折中的辦辦法。如如Piccturre問(wèn)題題中的GGrouup_TTYPEE.Coountt過(guò)程的的4、5兩步，要要求出某某個(gè)矩形形邊對(duì)應(yīng)應(yīng)的映射射編號(hào)。我我們定義義的映射射僅僅是是編號(hào)坐坐標(biāo)值，并并不是坐坐標(biāo)值編編號(hào)。如如果再實(shí)實(shí)現(xiàn)這一一映射，勢(shì)勢(shì)必增加加編程難難度。所所以編程程求精時(shí)時(shí)，可以以認(rèn)為以以整數(shù)而而不是以以頂點(diǎn)坐坐標(biāo)對(duì)平平面進(jìn)行行橫向切切割。這這樣映射射關(guān)系很很好建立立，坐標(biāo)標(biāo)值本身身就是編編號(hào)，減減少了編編程難度度。如果果進(jìn)一步步以頂點(diǎn)點(diǎn)坐標(biāo)作作橫向切切割，當(dāng)當(dāng)然會(huì)提提高程序序效率，但但效果并并不明顯顯——掃掃描計(jì)數(shù)數(shù)仍需要要O(NN)的時(shí)時(shí)間，這這是很昂昂貴的，所所以進(jìn)一一步切割割并不影影響算法法主要部部分的效效率，另另一方面面，編程程難度卻卻會(huì)大大大提高，得得不償失失。由此此看出，在在算法效效率“大大局已定定”的情情況下，有有時(shí)也需需要適當(dāng)當(dāng)?shù)貭奚绦蛐蕘?lái)減減少編程程不必要要的麻煩煩。44、靈活活應(yīng)用已已有知識(shí)識(shí)。我們們對(duì)編程程都積累累了一定定的經(jīng)驗(yàn)驗(yàn)，對(duì)以以后的解解題有很很大幫助助。一個(gè)個(gè)“新問(wèn)問(wèn)題”有有時(shí)與“舊舊問(wèn)題”有有許多內(nèi)內(nèi)在的聯(lián)聯(lián)系，往往往能夠夠?qū)⑿聠?wèn)問(wèn)題轉(zhuǎn)化化為所學(xué)學(xué)過(guò)的知知識(shí)，或或者由所所學(xué)過(guò)的的知識(shí)得得到啟發(fā)發(fā)，從而而解決問(wèn)問(wèn)題。所所謂“新新”數(shù)據(jù)據(jù)結(jié)構(gòu)的的構(gòu)造，有有時(shí)可以以是幾種種基本數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)的有機(jī)機(jī)結(jié)合，或或者由基基本數(shù)據(jù)據(jù)結(jié)構(gòu)得得到啟發(fā)發(fā)而得到到。做到到“溫故故而知新新”，是是對(duì)算法法設(shè)計(jì)者者創(chuàng)新意意識(shí)的要要求。當(dāng)當(dāng)然，對(duì)對(duì)一個(gè)問(wèn)問(wèn)題，要要首先考考慮現(xiàn)成成的、經(jīng)經(jīng)典的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)。如隊(duì)隊(duì)列、棧棧、鏈表表等等，其其標(biāo)準(zhǔn)結(jié)結(jié)構(gòu)與標(biāo)標(biāo)準(zhǔn)運(yùn)算算已經(jīng)有有了“公公論”，程程序?qū)崿F(xiàn)現(xiàn)也經(jīng)過(guò)過(guò)了“千千錘百煉煉”，效效率已經(jīng)經(jīng)很完美美。如果果找到一一種可行行的經(jīng)典典數(shù)據(jù)結(jié)結(jié)構(gòu)，那那么算法法實(shí)現(xiàn)一一般來(lái)說(shuō)說(shuō)就比較較輕松。要要做到這這一點(diǎn)，要要求我們們有扎實(shí)實(shí)的基礎(chǔ)礎(chǔ)知識(shí)，對(duì)對(duì)各種算算法及數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)了然于于胸。在在計(jì)數(shù)掃掃描過(guò)程程中采用用了經(jīng)典典的線性性一維數(shù)數(shù)組，是是一個(gè)很很自然的的考慮方方向，并并且可以以很容易易上機(jī)實(shí)實(shí)現(xiàn)，不不足之處處在于其其效率較較低?？偟貋?lái)說(shuō)，Picture問(wèn)題算法思想的方向還是基本正確的。Picture問(wèn)題最大數(shù)據(jù)應(yīng)包含近5000個(gè)矩形，這樣大的數(shù)據(jù)量決定了要降低規(guī)模是“大勢(shì)所趨”，所以對(duì)問(wèn)題的離散化處理是合理的選擇。至于效率不高，應(yīng)當(dāng)是線性數(shù)據(jù)結(jié)構(gòu)的選擇造成的。由此，我們可以看到使用線性結(jié)構(gòu)來(lái)實(shí)現(xiàn)Picture問(wèn)題還有一些缺陷，其中最主要的是各組超元線段的統(tǒng)計(jì)相互獨(dú)立，聯(lián)系不緊，這是算法效率不高的“瓶頸”。為了解決這個(gè)問(wèn)題，我們嘗試用其它的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)算法，像前面一樣，這個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)該符合以下的條件：11、同線線性結(jié)構(gòu)構(gòu)一樣，新新數(shù)據(jù)結(jié)結(jié)構(gòu)要適適用于描描述一組組超元線線段的狀狀態(tài)。至至少，新新結(jié)構(gòu)要要合理地地表示一一組超元元線段屬屬于輪廓廓的部分分，或者者說(shuō)它要要能準(zhǔn)確確地且較較快地計(jì)計(jì)算出算算式①中Bellongg(s))的值。22、新結(jié)結(jié)構(gòu)也要要與基本本算法相相適應(yīng)。新新結(jié)構(gòu)仍仍然以問(wèn)問(wèn)題的離離散化為為基礎(chǔ)，映映射結(jié)構(gòu)構(gòu)應(yīng)當(dāng)保保留———事實(shí)上上映射結(jié)結(jié)構(gòu)在時(shí)時(shí)間效率率上并沒(méi)沒(méi)有缺點(diǎn)點(diǎn)。新結(jié)結(jié)構(gòu)在描描述超元元線段組組時(shí)則要要設(shè)法將將不同組組超元線線段的統(tǒng)統(tǒng)計(jì)有機(jī)機(jī)結(jié)合起起來(lái)。33、新結(jié)結(jié)構(gòu)還要要兼顧編編程的方方便。如如果選擇擇的數(shù)據(jù)據(jù)結(jié)構(gòu)編編程難度度太大，以以至于無(wú)無(wú)法上機(jī)機(jī)實(shí)現(xiàn)，或或者只是是理論上上的“高高效率”，對(duì)對(duì)解題沒(méi)沒(méi)有實(shí)際際意義。這這么說(shuō)也也許太夸夸張，但但實(shí)際上上也常常常存在“魚(yú)魚(yú)與熊掌掌不可兼兼得”的的情況。大大部分高高級(jí)數(shù)據(jù)據(jù)結(jié)構(gòu)的的實(shí)現(xiàn)都都需要一一定的編編程技巧巧。就像像問(wèn)題在在時(shí)間效效率與空空間效率率上的矛矛盾一樣樣，算法法效率與與編程難難度也有有矛盾，一一般來(lái)說(shuō)說(shuō)算法效效率越高高，編程程難度也也會(huì)越大大。考慮慮新結(jié)構(gòu)構(gòu)時(shí)希望望能找到到實(shí)現(xiàn)較較為容易易的數(shù)據(jù)據(jù)結(jié)構(gòu)。綜合以上分分析，由由于線性性結(jié)構(gòu)并并不能給給我們帶帶來(lái)令人人滿意的的效率，所所以我們們嘗試用用樹(shù)形結(jié)結(jié)構(gòu)來(lái)描描述一組組超元線線段的狀狀態(tài)，實(shí)實(shí)現(xiàn)Piictuure問(wèn)問(wèn)題的基基本算法法。為了了提高效效率，采采用的樹(shù)樹(shù)結(jié)構(gòu)必必需是平平衡樹(shù)，我我們姑且且稱之為為“超元元線段樹(shù)樹(shù)”。Pictuure問(wèn)問(wèn)題的深深入討論論基于對(duì)數(shù)據(jù)據(jù)結(jié)構(gòu)選選擇的進(jìn)進(jìn)一步分分析，我我們來(lái)重重新考慮慮一下PPictturee問(wèn)題的的數(shù)據(jù)結(jié)結(jié)構(gòu)的選選擇，即即采用樹(shù)樹(shù)形結(jié)構(gòu)構(gòu)來(lái)描述述一組超超元線段段的狀態(tài)態(tài)。線段樹(shù)受到累計(jì)掃掃描過(guò)程程的啟發(fā)發(fā)，一組組超元線線段屬于于輪廓的的數(shù)目，它它與跨越越該組超超元線段段的矩形形的縱向向邊位置置關(guān)系密密切。不不妨把矩矩形的縱縱向邊投投影到Y(jié)Y軸上，這這樣就把把矩形的的縱向邊邊看作閉閉區(qū)間，并并稱之為為閉區(qū)間間Q。我們們以“線線段樹(shù)”的的樹(shù)形數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)來(lái)描述述閉區(qū)間間Q。作為為工具，先先簡(jiǎn)單研研究線段段樹(shù)的特特點(diǎn)。線段樹(shù)是描描述單個(gè)個(gè)或若干干區(qū)間并并的樹(shù)形形結(jié)構(gòu)，屬屬于平衡衡樹(shù)的一一種。使使用線段段樹(shù)要求求知道所所描述的的區(qū)間端端點(diǎn)可能能取到的的值。換換句話說(shuō)說(shuō)，設(shè)AA[1...N]]是從小小到大排排列的區(qū)區(qū)間端點(diǎn)點(diǎn)集合，對(duì)對(duì)于任意意一個(gè)待待描述的的閉區(qū)間間P=[[x,yy]，存存在1≤i≤j≤N使得x==a[ii]且y=aa[j]]，這里里i,j稱為為x,yy的編號(hào)號(hào)?？梢砸钥吹剑醇词故菍?shí)實(shí)數(shù)坐標(biāo)標(biāo)，在線線段樹(shù)中中也只有有整數(shù)含含義。以以下所說(shuō)說(shuō)的區(qū)間間[x,y]如如無(wú)特殊殊說(shuō)明，x、y均是整數(shù)，即原始區(qū)間頂點(diǎn)坐標(biāo)的編號(hào)。線段樹(shù)是一一棵二叉叉樹(shù)，將將數(shù)軸劃劃分成一一系列的的初等區(qū)區(qū)間[I,I+11]((I=11—N-11)。每每個(gè)初等等區(qū)間對(duì)對(duì)應(yīng)于線線段樹(shù)的的一個(gè)葉葉結(jié)點(diǎn)。線線段樹(shù)的的內(nèi)部結(jié)結(jié)點(diǎn)對(duì)應(yīng)應(yīng)于形如如[I,,JJ]((J––I>11)的一一般區(qū)間間。一般般情況下下，線段段樹(shù)的結(jié)結(jié)點(diǎn)類型型定義如如下：TyppeLiness_Trree=OObjeecti,j::iinteegerr;{{結(jié)點(diǎn)表表示的區(qū)區(qū)間的頂頂點(diǎn)標(biāo)號(hào)號(hào)I,J}couunt:inntegger;;{覆蓋這這一結(jié)點(diǎn)點(diǎn)的區(qū)間間數(shù)}lefftchhildd,rigghtcchilld:↑Linnes__Treee;{二叉叉樹(shù)的兩兩個(gè)子結(jié)結(jié)點(diǎn)}end關(guān)于Linnes__Treee的其其它數(shù)據(jù)據(jù)域與定定義的運(yùn)運(yùn)算將陸陸續(xù)添加加。圖88是一棵棵線段樹(shù)樹(shù)，描述述的區(qū)間間端點(diǎn)可可以有110種取取值。其其中記錄錄著一個(gè)個(gè)區(qū)間[[3，6]，它它用紅色色的[33，5]及[5，6]的并并采表示示。圖中中紅色結(jié)結(jié)點(diǎn)的ccounnt域值值為1，黑色色結(jié)點(diǎn)的的couunt域域值為00。圖8直觀地看，子子結(jié)點(diǎn)就就是父結(jié)結(jié)點(diǎn)區(qū)間間平均分分成兩部部分。設(shè)設(shè)L,R是父父結(jié)點(diǎn)的的區(qū)間端端點(diǎn)，我我們可以以增加LLinees_TTreee.Buuildd(l,,r:iinteegerr)遞歸歸地定義義線段樹(shù)樹(shù)如下::ProceedurreLinnes__treee.BBuilld(ll,rr:inttegeer)Il{{左端點(diǎn)點(diǎn)}Jr{{右端點(diǎn)點(diǎn)}Countt0{初初始化}}Ifrr-l>1{{是否需需要生成成子結(jié)點(diǎn)點(diǎn)，若rr-l==1則是是初等區(qū)區(qū)間}theenk(l+r)){平平均分為為兩部分分}neew(llefttchiild))leeftcchilld↑.Buuildd(l,,k)){建建立左子子樹(shù)}neew(rrighhtchhildd)riighttchiild↑↑.Buuildd(k,,r)){建立立右子樹(shù)樹(shù)}elsseleeftcchilldnnilrigghtcchilldnnil設(shè)根結(jié)點(diǎn)是是Rooot，建建樹(shù)需要要執(zhí)行RRoott.Buuildd。由遞歸定義義看出，線線段樹(shù)是是一棵平平衡樹(shù)，高高度為┌┌l(fā)oggN┐。建立立整棵樹(shù)樹(shù)需要的的時(shí)間為為O(NN)。以上著重說(shuō)說(shuō)明了線線段樹(shù)的的存儲(chǔ)原原理，我我們還應(yīng)應(yīng)建立線線段樹(shù)的的基本運(yùn)運(yùn)算。線段樹(shù)可以以存儲(chǔ)多多個(gè)區(qū)間間，所以以支持區(qū)區(qū)間插入入運(yùn)算LLinees_TTreee.Innserrt(ll,rr:inttegeer)，定定義如下下：ProceedurreLinnes__Treee.IInseert((l,r:inttegeer){[l,r]]是待插插入?yún)^(qū)間間，l、r都是原原始頂點(diǎn)點(diǎn)坐標(biāo)}}if((l<=a[[i]))aand((a[jj]<=r))theencouuntcouunt+1{{蓋滿整整個(gè)結(jié)點(diǎn)點(diǎn)區(qū)間}}elsseifl<aa[(ii++jj)divv22]{是否否能覆蓋蓋到左孩孩子結(jié)點(diǎn)點(diǎn)區(qū)間}}tthennllefttchiild↑↑.Innserrt(ll,rr){向向左孩子子插入}}iifr>>a[[(i+j))diiv2]{是否否能覆蓋蓋到右孩孩子結(jié)點(diǎn)點(diǎn)區(qū)間}}tthennrrighhtchhildd↑.Innserrt(ll,r){向向右孩子子插入}}類似地，線線段樹(shù)支支持區(qū)間間的刪除除Linnes__Treee.DDeleete((l,r::inntegger))，定義義如下：：ProceedurreLinnes__Treee.DDeleete((l,r:inttegeer){[l,r]]是待刪刪除區(qū)間間，l、r都是原原始頂點(diǎn)點(diǎn)坐標(biāo)}}if((l<=a[[i]))aand((a[jj]<=r))theencouuntcouunt-1{{蓋滿整整個(gè)結(jié)點(diǎn)點(diǎn)區(qū)間}}elsseifl<aa[(ii++jj)divv22]{是否否能覆蓋蓋到左孩孩子結(jié)點(diǎn)點(diǎn)區(qū)間}}tthennllefttchiild↑↑.Deelette(ll,r){{向左孩孩子刪除除}iifr>>a[[(i+j))ddiv2]{是否否能覆蓋蓋到右孩孩子結(jié)點(diǎn)點(diǎn)區(qū)間}}tthennrrighhtchhildd↑.Deelette(ll,rr){向右右孩子刪刪除}執(zhí)行Linnes__Treee.DDeleete((l,r::inntegger))的先決決條件是是區(qū)間[[l,r]曾曾被插入入且還未未刪除。如如果建樹(shù)樹(shù)后插入入?yún)^(qū)間[[2，5]而刪刪除區(qū)間間[3，4]是非非法的。通過(guò)分析插插入與刪刪除的路路徑，可可知Liiness_Trree..Inssertt與Linnes__Treee.DDeleete的的時(shí)間復(fù)復(fù)雜度均均為O((loggN)。(詳見(jiàn)[附錄1]])由于線段樹(shù)樹(shù)給每一一個(gè)區(qū)間間都分配配了結(jié)點(diǎn)點(diǎn)，利用用線段樹(shù)樹(shù)可以求求區(qū)間并并后的測(cè)測(cè)度與區(qū)區(qū)間并后后的連續(xù)續(xù)段數(shù)。測(cè)度由于線段樹(shù)樹(shù)結(jié)構(gòu)遞遞歸定義義，其測(cè)測(cè)度也可可以遞歸歸定義。增增加數(shù)據(jù)據(jù)域Liiness_Trree..M表示示以該結(jié)結(jié)點(diǎn)為根根的子樹(shù)樹(shù)的測(cè)度度。M取值如如下：a[[j]–aa[i]]該結(jié)點(diǎn)點(diǎn)Couunt>>0M=0該結(jié)點(diǎn)點(diǎn)為葉結(jié)結(jié)點(diǎn)且CCounnt=00Leeftcchilld↑.M+RRighhtchhildd↑.M該結(jié)點(diǎn)點(diǎn)為內(nèi)部部結(jié)點(diǎn)且且Couunt==0據(jù)此，可以以用Liiness_Trree..UpDDataa來(lái)動(dòng)態(tài)態(tài)地維護(hù)護(hù)Linnes__Treee.MM。UpDDataa在每一一次執(zhí)行行Inssertt或Delletee之后執(zhí)執(zhí)行。定定義如下下：ProceedurreLinnes__Treee.UUpDaataifccounnt>0theenMaa[j]]––[[i]{{蓋滿區(qū)區(qū)間，測(cè)測(cè)度為aa[j]]–a[ii]}elsseifj-i=1{{是否葉葉結(jié)點(diǎn)}}tthennMM0{該結(jié)點(diǎn)點(diǎn)是葉結(jié)結(jié)點(diǎn)}eelseeMMLeeftcchilld↑.M+Riighttchiild↑↑.M

{{內(nèi)部結(jié)結(jié)點(diǎn)}UpDatta的復(fù)復(fù)雜度為為O(11)，則則用UppDatta來(lái)動(dòng)動(dòng)態(tài)維護(hù)護(hù)測(cè)度后后執(zhí)行根根結(jié)點(diǎn)的的Inssertt與Delletee的復(fù)雜雜度仍為為O(llogNN)。連續(xù)段數(shù)這里的連續(xù)續(xù)段數(shù)指指的是區(qū)區(qū)間的并并可以分分解為多多少個(gè)獨(dú)獨(dú)立的區(qū)區(qū)間。如如[1，2]∪[[2，33]∪[[5，6]可以以分解為為兩個(gè)區(qū)區(qū)間[11，3]與[5，6]，則則連續(xù)段段數(shù)為22。增加加一個(gè)數(shù)數(shù)據(jù)域LLinees_TTreee.liine表表示該結(jié)結(jié)點(diǎn)的連連續(xù)段數(shù)數(shù)。Liine的的討論比比較復(fù)雜雜，內(nèi)部部結(jié)點(diǎn)不不能簡(jiǎn)單單地將左左右孩子子的Liine相相加。所所以再增增加Liiness_Trree..lbdd與Linnes__Treee.rrbd域域。定義義如下：：1左端點(diǎn)點(diǎn)I被描述述區(qū)間蓋蓋到lbd=0左端點(diǎn)點(diǎn)I不被描描述區(qū)間間蓋到1右端端點(diǎn)J被描述述區(qū)間蓋蓋到rbd=0右端點(diǎn)點(diǎn)J不被描描述區(qū)間間蓋到lbd與rrbd的的實(shí)現(xiàn)：：11該該結(jié)點(diǎn)ccounnt>>0lbd=00該該結(jié)點(diǎn)是是葉結(jié)點(diǎn)點(diǎn)且coountt=0llefttchiild↑↑.lbbd該該結(jié)點(diǎn)是是內(nèi)部結(jié)結(jié)點(diǎn)且CCounnt=0011該該結(jié)點(diǎn)ccounnt>>0rbd=00該該結(jié)點(diǎn)是是葉結(jié)點(diǎn)點(diǎn)且coountt=0rrighhtchhildd↑.rbbd該結(jié)結(jié)點(diǎn)是內(nèi)內(nèi)部結(jié)點(diǎn)點(diǎn)且Coountt=0有了lbdd與rbdd，Linne域就就可以定定義了：：1該結(jié)點(diǎn)點(diǎn)couunt>00Line=0該結(jié)結(jié)點(diǎn)是葉葉結(jié)點(diǎn)且且couunt=00Lefftchhildd↑.Liine+Riighttchiild↑↑.Liine-1

結(jié)內(nèi)點(diǎn)otfhdb=且gclb=Leeftcchilld↑.Liine+Riighttchiild↑↑.Liine

該是結(jié)Cn0fhdbgclb都據(jù)此，可以以定義UUpDaata’’動(dòng)態(tài)地地維護(hù)LLinee域。與與UpDDataa相似，UUpDaata’’也在每每一次執(zhí)執(zhí)行Innserrt或Delletee后執(zhí)行行。定義義如下：：ProceedurreLinnes__Treee.UUpDaata’’ifccounnt>0{是否蓋蓋滿結(jié)點(diǎn)點(diǎn)表示的的區(qū)間}}theenlbdd1rrbd1LLinee1elsseifj-i=1{是否否為葉結(jié)結(jié)點(diǎn)}tthennllbd0{{進(jìn)行到到這一步步，如果果為葉結(jié)結(jié)點(diǎn)，

ccounnt==0}}rrbd0llinee0eelseellineeLLefttchiild↑↑.liine+Riighttchiild↑↑.liine-Leeftcchilld↑.rbbd**Riighttchiild↑↑.lbbd{用乘法確確定Leeftcchilld↑.rbbd與Rigghtcchilld↑.lbbd是否否同時(shí)為為1}同時(shí)，由于于增加了了Linne、M等幾個(gè)個(gè)數(shù)據(jù)域域，在建建樹(shù)Liiness_Trree..Buiild時(shí)時(shí)要將新新增的域域初始化化。至此，線段段樹(shù)構(gòu)造造完畢，完完整的線線段樹(shù)定定義如下下：Liness_Trree=oobjeecti,j:inntegger;;couunt:inntegger;;linne::iinteegerr;lbdd,rrbd:byyte;;m::iinteegerr;lefftchhildd,rigghtcchilld:↑Linnes__treee;prooceddureeBBuilld(ll,rr:inttegeer);;prooceddureeIInseert((l,r::inntegger));prooceddureeDDeleete((l,r::inntegger));prooceddureeUUpDaata;;prooceddureeUUpDaata’’;end有了線段樹(shù)樹(shù)這個(gè)工工具，可可以考慮慮利用樹(shù)樹(shù)形結(jié)構(gòu)構(gòu)來(lái)描述述一組超超元線段段的狀態(tài)態(tài)。Pictuure問(wèn)問(wèn)題的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)選擇之之二：樹(shù)樹(shù)形結(jié)構(gòu)構(gòu)采用線性結(jié)結(jié)構(gòu)描述述一組超超元線段段的狀態(tài)態(tài)并不能能帶來(lái)太太高的效效率，其其中主要要原因是是各組超超元線段段聯(lián)系不不緊。如如圖9所示，超超元線段段CD與EF被矩矩形AGGHB遮遮蓋，不不屬于輪輪廓；而而與之相相鄰DDD’與FF’’則“擺擺脫”了了矩形的的遮蓋，屬屬于輪廓廓的一部部分。

圖9圖圖10由此類推，可可以看出出相鄰的的超元線線段組都都有類似似的問(wèn)題題。如圖圖9，DD’’與FF’’不被遮遮蓋，可可以這樣樣分析：：從左往往右，CCD、EF首先先被遮蓋蓋，但隨隨著B(niǎo)FF的出現(xiàn)現(xiàn)，對(duì)DDD’、FF’’的遮蓋蓋自然消消失。這這一點(diǎn)，正正是相鄰鄰超元線線段組的的內(nèi)在聯(lián)聯(lián)系。用用線性結(jié)結(jié)構(gòu)無(wú)法法表示出出這一聯(lián)聯(lián)系，因因?yàn)楦鹘M組的累計(jì)計(jì)掃描過(guò)過(guò)程是獨(dú)獨(dú)立的?，F(xiàn)現(xiàn)在我們們用樹(shù)形形結(jié)構(gòu)來(lái)來(lái)表示將將較好地地解決這這一問(wèn)題題，因?yàn)闉榫€段樹(shù)樹(shù)支持插插入與刪刪除及動(dòng)動(dòng)態(tài)維護(hù)護(hù)，可以以有機(jī)聯(lián)聯(lián)系各組組超元線線段的狀狀態(tài)。我我們把“從從左往右右”當(dāng)作作一個(gè)掃掃描的過(guò)過(guò)程，若若將其嚴(yán)嚴(yán)格地描描述，可可以得到到一個(gè)稱稱為線段段掃描的的過(guò)程：：設(shè)立掃描線線段L。L從左往右右掃描，停停留在每每一超元元線段組組上。如如圖100所示。L的狀態(tài)用用線段樹(shù)樹(shù)來(lái)表示示，每一一條縱向向的矩形形邊看作作一個(gè)待待合并區(qū)區(qū)間。線線段樹(shù)的的連續(xù)段段數(shù)*22表示該該組超元元線段屬屬于輪廓廓的線段段數(shù)目。如如圖100，L的狀態(tài)態(tài)首先是是[G,AA]∪[E,,C]，連連續(xù)線段段數(shù)是11，所以以1*22=2是是該組超超元線段段屬于輪輪廓的數(shù)數(shù)目。接接著L進(jìn)一步步掃描，狀狀態(tài)改變變?yōu)閇EE,C]],連續(xù)線線段數(shù)是是1，所以以該組超超元線段段屬于輪輪廓的數(shù)數(shù)目也是是1*22=2。這這樣，上上文所說(shuō)說(shuō)的“超超元線段段樹(shù)”就就用線段段樹(shù)來(lái)實(shí)實(shí)現(xiàn)。為為了統(tǒng)一一起見(jiàn)，以以后仍稱稱線段樹(shù)樹(shù)。掃描過(guò)程中中動(dòng)態(tài)地地維護(hù)LL的狀態(tài)態(tài)。參看看圖100，L狀態(tài)的的轉(zhuǎn)換是是在線段段樹(shù)中刪刪去區(qū)間間[H,BB]即[G,,A]造造成的。歸歸納一下下，有以以下結(jié)論論：L初始化為為空，即即線段樹(shù)樹(shù)剛建好好時(shí)的情情形。掃描時(shí)，遇遇到矩形形左邊，將將其插入入（Innserrt）線線段樹(shù)。掃描時(shí)，遇遇到矩形形右邊，將將其從線線段樹(shù)中中刪除（Delete）。由于從左往右掃描，事先插入了該矩形的左邊，所以刪除合法。參看算式①①，以上上的線段段掃描過(guò)過(guò)程可以以得到每每一組超超元線段段的Beelonng(ss)，進(jìn)進(jìn)一步得得到整個(gè)個(gè)圖形輪輪廓的橫橫向邊長(zhǎng)長(zhǎng)。同時(shí)時(shí)，線段段掃描過(guò)過(guò)程還可可以在一一次從左左到右的的掃描中中求得圖圖形輪廓廓的縱向向邊長(zhǎng)。還還以圖110為例例。在掃掃描線狀狀態(tài)改變變之前，L是[G,A]∪[E,C]；改變狀態(tài)之后，[H,F]、[D,B]就“露”了出來(lái)，成為輪廓一部分。[G,A]∪[E,C]正是L改變前后測(cè)度的差。如果描述相鄰的掃描線狀態(tài)的線段樹(shù)分別為Tree1、Tree2，則掃描過(guò)程中“露出”的縱向邊長(zhǎng)度為|Tree1.M–Tree2.M|。在掃描過(guò)程程中，遇遇到的插插入或刪刪除稱為為“事件件”，待待插入或或刪除的的線段稱稱為“事事件線段段”。在在掃描之之前，應(yīng)應(yīng)將事件件按橫坐坐標(biāo)從小小到大排排序。（詳詳見(jiàn)[附錄2]]）通過(guò)以上分分析，得得到較之之線性結(jié)結(jié)構(gòu)的累累計(jì)掃描描過(guò)程改改進(jìn)的線線段掃描描過(guò)程的的算法：：以矩形頂點(diǎn)點(diǎn)坐標(biāo)切切割平面面，實(shí)現(xiàn)現(xiàn)橫縱坐坐標(biāo)的離離散化并并建立映映射X__Mapp、Y_MMap。事件排序Root..Buiild((1,N*22)Nowm00NowLiine0Ans0forI1to事件件的最大大編號(hào)doiifI是插插入事件件tthennRRoott.Innserrt(YY_Maap.CCoorrd[事事件線段段頂點(diǎn)11]，

Y__Mapp.Cooordd[事件件線段頂頂點(diǎn)2]])eelseeRRoott.Deelette(YY_Maap.CCoorrd[事事件線段段頂點(diǎn)11]，

Y_MMap..C