剖析線段樹與矩形切割

解決動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題的兩把利刃 剖析線段樹與矩形切割 廣東北江中學(xué) 薛矛【關(guān)鍵字】 線段樹 矩形樹 方塊樹 線段切割 矩形切割【摘要】本文從統(tǒng)計(jì)類型的問(wèn)題出發(fā)，以更好地解決這類問(wèn)題為目的，較詳細(xì)地介紹了線段樹的基本操作，改進(jìn)和推廣；矩形切割的思想以及具體的使用方法。并通過(guò)將線段樹和矩形切割進(jìn)行對(duì)比，分析了線段樹和矩形切割的復(fù)雜度，優(yōu)缺點(diǎn)等，提出了它們各自的適用范圍，并總結(jié)出何時(shí)使用最合適。【目錄】一、引言2二、線段樹22.1 線段樹的結(jié)構(gòu)22.2 線段樹的建立32.3 線段樹中的線段插入和刪除32.3.1 線段的插入32.3.2 線段的刪除42.4 線段樹的簡(jiǎn)單應(yīng)用42.5 線段樹的改進(jìn)52.6 線段樹的推廣92.7 線段樹小結(jié)10三、矩形切割103.1 線段切割103.1.1 線段的數(shù)據(jù)結(jié)構(gòu)113.1.2 判斷線段相交的函數(shù)113.1.3 切割線段的過(guò)程113.2 矩形切割123.3 矩形切割的推廣133.4 矩形切割的應(yīng)用15四、線段樹與矩形切割的比較164.1 線段樹的時(shí)空復(fù)雜度174.1.1 線段樹的空間復(fù)雜度174.1.2 線段樹的時(shí)間復(fù)雜度174.2矩形切割的時(shí)空復(fù)雜度174.2.1矩形切割的空間復(fù)雜度174.2.2 矩形切割的時(shí)間復(fù)雜度184.3 線段樹與矩形切割適用范圍的比較19五、總結(jié)19【正文】一、引言 我們?cè)谧鼍毩?xí)和比賽中，經(jīng)常能碰見統(tǒng)計(jì)類型的題目。題目通過(guò)輸入數(shù)據(jù)給程序提供事物信息，并要求程序能比較高效地求出某些時(shí)刻，某種情況下，事物的狀態(tài)是怎樣的。這類問(wèn)題往往比較簡(jiǎn)單明了，也能十分容易地寫出模擬程序。但較大的數(shù)據(jù)規(guī)模使得模擬往往不能滿足要求。于是我們就要尋找更好的方法。本文將介紹解決此類問(wèn)題的兩種方法線段樹與矩形切割。二、線段樹線段樹已經(jīng)不是一個(gè)陌生的名詞了，相信大家也對(duì)線段樹比較熟悉，這里只做簡(jiǎn)要的介紹。2.1 線段樹的結(jié)構(gòu) 線段樹是一棵二叉樹，其結(jié)點(diǎn)是一條“線段”a,b，它的左兒子和右兒子分別是這條線段的左半段和右半段，即a, 和,b。線段樹的葉子結(jié)點(diǎn)是長(zhǎng)度為1的單位線段a,a+1。下圖就是一棵根為1,10的線段樹：易證一棵以a,b為根的線段樹結(jié)點(diǎn)數(shù)是2*(b-a)-1。由于線段樹是一棵平衡樹，因此一棵以a,b為根結(jié)點(diǎn)的線段樹的深度為log2(2*(b-a)。線段樹中的結(jié)點(diǎn)一般采取如下數(shù)據(jù)結(jié)構(gòu)：Type TreeNode=Record a,b,Left,Right:Longint End其中a,b分別表示線段的左端點(diǎn)和右端點(diǎn)，Left，Right表示左兒子和右兒子的編號(hào)。因此我們可以用一個(gè)一維數(shù)組來(lái)表示一棵線段樹：Tree:array1.Maxn of TreeNode;a,b,Left,Right這4個(gè)域是描述一棵線段樹所必須的4個(gè)量。根據(jù)實(shí)際需要，我們可以增加其它的域，例如增加Cover域來(lái)計(jì)算該線段被覆蓋的次數(shù)，bj域用來(lái)表示結(jié)點(diǎn)的修改標(biāo)記（后面將會(huì)提到）等等。2.2 線段樹的建立 我們可以用一個(gè)簡(jiǎn)單的過(guò)程建立一棵線段樹。Procedure MakeTree(a,b)Var Now:LongintBegintot tot + 1Now totTreeNow.a aTreeNow.b bIf a +1 b thenTreeNow.Left tot + 1MakeTree(a, )TreeNow.Right tot + 1MakeTree( , b)End2.3 線段樹中的線段插入和刪除 增加一個(gè)Cover的域來(lái)計(jì)算一條線段被覆蓋的次數(shù)，即數(shù)據(jù)結(jié)構(gòu)變?yōu)椋篢ype TreeNode=Record a,b,Left,Right,Cover:Longint End因此在MakeTree的時(shí)候應(yīng)順便把Cover置0。2.3.1 線段的插入插入一條線段c,dProcedure Insert(Num)Begin If (cTreeNum.a)and(TreeNum.bd) then TreeNum.Cover TreeNum.Cover + 1 Else If c then Insert(TreeNum.Right)End 2.3.2 線段的刪除 刪除一條線段c,dProcedure Delete(Num)Begin If (cTreeNum.a)and(TreeNum.bd) then TreeNum.Cover TreeNum.Cover - 1 Else If c then Delete(TreeNum.Right)End2.4 線段樹的簡(jiǎn)單應(yīng)用 掌握了線段樹的建立，插入和刪除這3條操作，就能用線段樹解決一些最基本的統(tǒng)計(jì)問(wèn)題了。例如給出一系列線段a,b (0ab0 then Number Number + (TreeNum.b-TreeNUM.a) Else Count(TreeNum.Left) Count(TreeNum.Right)End 像這樣的基本靜態(tài)統(tǒng)計(jì)問(wèn)題，線段樹是可以很方便快捷地解決的。但是我們會(huì)留意到，如果處理一些動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題，比如說(shuō)一些需要用到刪除和修改的統(tǒng)計(jì)，困難就出現(xiàn)了。例1在數(shù)軸上進(jìn)行一系列操作。每次操作有兩種類型，一種是在線段a,b上涂上顏色，另一種將a,b上的顏色擦去。問(wèn)經(jīng)過(guò)一系列的操作后，有多少條單位線段k,k+1被涂上了顏色。這時(shí)我們就面臨了一個(gè)問(wèn)題線段的刪除。但線段樹中線段的刪除只能是把已經(jīng)放入的線段刪掉，例如我們沒(méi)有放置3,6這條線段，刪除3,6就是無(wú)法做到的了。而這道題目則不同，例如在1,15上涂了顏色，我們可以把4,9上的顏色擦去，但線段樹中只是插入了1,15這條線段，要?jiǎng)h除4,9這條線段顯然是做不到的。因此，我們有必要對(duì)線段樹進(jìn)行改進(jìn)。2.5 線段樹的改進(jìn) 用回剛剛那個(gè)例子。給1,15涂上色后，再把4,9的顏色擦去。很明顯1,15這條線段已經(jīng)不復(fù)存在，只剩下1,4和9,15，所以我們必須對(duì)線段樹進(jìn)行修改，才能使它符合改變了的現(xiàn)實(shí)。我們不難想到把1,15這條線段刪去，再插入線段1,4和9,15。但事實(shí)上并非如此簡(jiǎn)單。如下圖 若先前我們已經(jīng)插入了線段8,11，1,8。按上面的做法，只把1,15刪去，然后插入1,4，9,15的話，1,8，8,11這兩條線段并沒(méi)有刪去，但明顯與實(shí)際不符了。于是1,8，8,11也要修改。這時(shí)疑問(wèn)就來(lái)了。若以線段1,15為根的整棵線段樹中的所有結(jié)點(diǎn)之前都已經(jīng)插入過(guò)，即我們?cè)?jīng)這樣涂過(guò)顏色：1,2,2,3，14,15,1,3,3,5,13,15,1,5，1,15。然后把1,15上的顏色擦去。那么整個(gè)線段樹中的所有結(jié)點(diǎn)的狀態(tài)就都與實(shí)際不符了，全都需要修改。修改的復(fù)雜度就是線段樹的結(jié)點(diǎn)數(shù)，即2*(15-1)=28。如果不是1,15這樣的小線段，而是1,30000這樣的線段，一個(gè)擦除動(dòng)作就需要O(59998)的復(fù)雜度去修改，顯然效率十分低（比直接模擬的O(30000)還差）。為了解決這個(gè)問(wèn)題，我們給線段樹的每一個(gè)結(jié)點(diǎn)增加一個(gè)標(biāo)記域（以下用bj來(lái)表示標(biāo)記域）。增加一個(gè)標(biāo)記域有什么用呢？如下圖：以1,5為根的整棵線段樹的全部結(jié)點(diǎn)都已涂色?，F(xiàn)把1,5上的顏色擦去。則整棵線段樹的結(jié)點(diǎn)的狀態(tài)都與實(shí)際不符了。可是我們并不一定要對(duì)所有結(jié)點(diǎn)都進(jìn)行修改，因?yàn)橛行┙Y(jié)點(diǎn)以后可能根本不會(huì)有被用到的時(shí)候。例如我們做完擦去1,5的操作之后，只是想詢問(wèn)3,5是否有涂上顏色。那么我們對(duì)1,2，2,3,1,3,3,4,4,5等線段的修改就變成無(wú)用功了。為了避免無(wú)用功的出現(xiàn)，我們引入標(biāo)記域bj。具體操作如下：1、 擦去線段a,b之后，給它的左兒子和右兒子都做上標(biāo)記，令它們的bj=-1。2、 每次訪問(wèn)一條線段，首先檢查它是否被標(biāo)記，若其bj=-1，則進(jìn)行如下操作： 將該線段的狀態(tài)改為未被覆蓋，并把該線段設(shè)為未被標(biāo)記，bj=0。 把該線段的左右兒子都設(shè)為被標(biāo)記，bj=-1。對(duì)線段1,5進(jìn)行了這樣的操作后就不需要對(duì)整棵線段樹都進(jìn)行修改了。原理很簡(jiǎn)單。以線段3,4為例。若以后有必要訪問(wèn)3,4，則必然先訪問(wèn)到它的父親3,5，而3,5的bj=-1，因此進(jìn)行、的操作后，3,5的狀態(tài)變?yōu)槲幢桓采w，并且把他的標(biāo)記傳遞給了他的兒子3,4和4,5。接著訪問(wèn)3,4的時(shí)候，它的bj=-1，我們又把3,4的狀態(tài)變?yōu)槲幢桓采w?？梢?，標(biāo)記會(huì)順著訪問(wèn)3,4的路一直傳遞到3,4，使得我們知道要對(duì)3,4的狀態(tài)進(jìn)行修改，避免了錯(cuò)誤的產(chǎn)生。同時(shí)，當(dāng)我們需要用到3,4的時(shí)候才會(huì)進(jìn)行修改，如果根本不需要用它，修不修改都無(wú)所謂了，并不會(huì)影響程序的正確性。因此這種方法在保持了正確性的同時(shí)有避免了無(wú)意義的操作，提高了程序的效率。進(jìn)行標(biāo)記更新的代碼如下：Procedure Clear(Num)Begin TreeNum.Cover 0 TreeNum.bj 0 TreeTreeNum.Left.bj -1 TreeTreeNum.Right.bj -1End每次訪問(wèn)線段a,b之前，首先檢查它是否被標(biāo)記，如果是則調(diào)用過(guò)程Clear進(jìn)行狀態(tài)修改。這樣做只是在訪問(wèn)的時(shí)候順便進(jìn)行修改，復(fù)雜度是O(1)，程序效率依然很高。于是，引入標(biāo)記域后，本題中插入和刪除的過(guò)程大致如下：插入過(guò)程 Insert1、若該線段被標(biāo)記，則調(diào)用Clear過(guò)程2、若線段狀態(tài)為被涂色，則退出過(guò)程（線段已被涂色，無(wú)需再插入它或它的子線段）3、若涂色的區(qū)域覆蓋了該線段，則該線段的狀態(tài)變?yōu)楸煌可?，并退出過(guò)程4、若涂色的區(qū)域與該線段的左半截的交集非空，則調(diào)用左兒子的插入過(guò)程5、若涂色的區(qū)域與該線段的右半截的交集非空，則調(diào)用右兒子的插入過(guò)程刪除過(guò)程 Delete 1、若該線段被標(biāo)記，則退出過(guò)程（該線段已被賦予被擦除的“義務(wù)”，無(wú)需再次賦予） 2、若擦除的區(qū)域覆蓋了該線段，則該線段的狀態(tài)變?yōu)槲幢煌可?，并將其左右兒子都做上?biāo)記，退出過(guò)程線段a,b狀態(tài)為被涂色，而擦除c,d相當(dāng)于把a(bǔ),b整段擦除，再插入a,c（若ac）和d,b（若db）3、若該線段的狀態(tài)為被涂色，則 該線段狀態(tài)變?yōu)槲幢煌可?將其左右兒子做上標(biāo)記 插入線段a,c和d,b 4、若該線段的狀態(tài)為未被涂色，則若擦除區(qū)域與該線段的左半截的交集非空，則調(diào)用左兒子的擦除過(guò)程 若擦除區(qū)域與該線段的右半截的交集非空，則調(diào)用右兒子的擦除過(guò)程程序請(qǐng)參見附錄 歸納一下標(biāo)記域的思想及如何使用。如果我們對(duì)整條線段a,b進(jìn)行操作的話，我們就可以只是給a,b的左右兒子做上標(biāo)記，而無(wú)需對(duì)以a,b為根的整棵子樹中的所有結(jié)點(diǎn)進(jìn)行修改。原理就是對(duì)下面的所有結(jié)點(diǎn)c,d，都有c,da,b，因此a,b狀態(tài)的改變也就代表了c,d狀態(tài)的改變。 本著這個(gè)思想，標(biāo)記域的使用形式并不是固定的，而是多樣的，具體形式如何要視題目而定，但只要理解了它的思想，總能想到如何確定作標(biāo)記的方式，維持線段樹的高效。例如下面這一題：例2Byteotian州鐵道部決定趕上時(shí)代，為此他們引進(jìn)了城市聯(lián)網(wǎng)。假設(shè)城市聯(lián)網(wǎng)順次連接著 n 個(gè)城市，從1到 n 編號(hào)(起始城市編號(hào)為1，終止城市編號(hào)為n)。每輛火車有m個(gè)座位且在任何兩個(gè)車站之間運(yùn)送更多的乘客是不允許的。電腦系統(tǒng)將收到連續(xù)的預(yù)訂請(qǐng)求并決定是否滿足他們的請(qǐng)求。當(dāng)火車在被請(qǐng)求的路段上有足夠的空位時(shí)，就通過(guò)這個(gè)請(qǐng)求，否則不通過(guò)。通過(guò)請(qǐng)求的一部分是不允許的。通過(guò)一個(gè)請(qǐng)求之后，火車?yán)锏目瘴粩?shù)目將得到更新。請(qǐng)求應(yīng)按照收到的順序依次處理。 任務(wù)：計(jì)算哪些請(qǐng)求可以通過(guò)，哪些請(qǐng)求不能通過(guò)。輸入文件 第一行是三個(gè)被空格隔開整數(shù)n, m 和 r (1=n=60 000, 1=m=60 000, 1=r=60 000)。數(shù)字分別表示：鐵路上的城市個(gè)數(shù)，火車內(nèi)的座位數(shù)，請(qǐng)求的數(shù)目。接下來(lái)r行是連竄的請(qǐng)求。第i+1行描述第i個(gè)請(qǐng)求。描述包含三個(gè)整數(shù)k1、k2 和 v (1=k1k2=n, 1=v=m)。它們分別表示起點(diǎn)車站的編號(hào)，目標(biāo)車站的編號(hào)，座位的需求數(shù)。輸出文件 輸出r行，每行一個(gè)字符。T表示可以通過(guò)；F表示不能通過(guò)。樣例輸入4 6 41 4 21 3 22 4 31 2 3樣例輸出TTNN 這道題需要判斷請(qǐng)求是否能被滿足，即涉及到線段狀態(tài)的詢問(wèn)。當(dāng)要求被滿足的時(shí)候要減去相應(yīng)線段上的座位數(shù)，因此涉及到線段的動(dòng)態(tài)修改。于是我們同樣可以引入標(biāo)記域來(lái)維持動(dòng)態(tài)修改算法的高效。 由于該題的特點(diǎn)在于詢問(wèn)上。為了詢問(wèn)能夠高效，我們用Seat這個(gè)域來(lái)記錄線段a,b上的座位數(shù)，因此在建立線段樹的時(shí)候，所有節(jié)點(diǎn)的Seat初始狀態(tài)為m。為了能實(shí)時(shí)反映線段a,b上剩下的座位數(shù)，當(dāng)a,b的左兒子或右兒子的狀態(tài)發(fā)生改變時(shí)，我們通過(guò)a,b.Seat = Min左兒子.Seat , 右兒子.Seat來(lái)對(duì)線段a,b的座位數(shù)進(jìn)行更新，即取a,b整條線段上所有座位數(shù)中的最小值作為線段a,b的座位數(shù)。 對(duì)于線段狀態(tài)的修改，仍然可以引入標(biāo)記域。如果我們要把結(jié)點(diǎn)a,b上的座位數(shù)都減去v，就滿足了對(duì)整條線段a,b進(jìn)行操作 的要求，因此可以將其左右兒子的bj都減去v。而在訪問(wèn)每條線段前先檢查其標(biāo)記是否為0，若不為0，則執(zhí)行Clear過(guò)程進(jìn)行更新。Procedure Clear(Num)Begin TreeNum.Seat TreeNum.Seat + TreeNum.bj TreeTreeNum.Left.bj TreeTreeNum.Left.bj + TreeNum.bj TreeTreeNum.Right.bj TreeTreeNum.Right.bj + TreeNum.bjTreeNum.bj 0End判斷請(qǐng)求能否通過(guò)的函數(shù)以及座位狀態(tài)修改的過(guò)程如下：判斷請(qǐng)求能否通過(guò)的函數(shù) Can(返回值為布爾類型)1、若線段標(biāo)記不為0，執(zhí)行Clear過(guò)程進(jìn)行更新 2、若請(qǐng)求區(qū)域覆蓋了該線段，則： 若座位數(shù)大于等于要求值，返回True，否則返回False 3、若請(qǐng)求區(qū)域跨越該線段的中點(diǎn)，則返回值 = Can(左兒子) Can(右兒子) 4、若請(qǐng)求區(qū)域在該線段中點(diǎn)的左方，則返回值 = Can(左兒子) 5、若請(qǐng)求區(qū)域在該線段中點(diǎn)的右方，則返回值 = Can(右兒子)座位狀態(tài)修改的過(guò)程 Delete 1、若線段標(biāo)記不為0，執(zhí)行Clear過(guò)程進(jìn)行更新 2、若請(qǐng)求區(qū)域覆蓋了該線段，則將該線段的座位數(shù)減去請(qǐng)求的座位數(shù)目v，并將左右兒子的標(biāo)記bj都減去v。退出過(guò)程。調(diào)用Clear過(guò)程，是因?yàn)榈?步中進(jìn)行座位數(shù)更新時(shí)需要用到左右兒子的座位數(shù)。而左右兒子的座位數(shù)并不一定符合實(shí)際情況（即它們的bj可能不為0），不更新就有可能產(chǎn)生錯(cuò)誤。 3、若請(qǐng)求區(qū)域與該線段左半截有交集，則 調(diào)用左兒子的Delete過(guò)程 否則調(diào)用左兒子的Clear過(guò)程進(jìn)行更新 4、若請(qǐng)求區(qū)域與該線段右半截有交集，則 調(diào)用右兒子的Delete過(guò)程 否則調(diào)用右兒子的Clear過(guò)程進(jìn)行更新 5、取左右兒子的座位數(shù)中較小的那個(gè)作為該線段的座位數(shù)程序請(qǐng)參見附錄2.6 線段樹的推廣 線段樹處理的是線性統(tǒng)計(jì)問(wèn)題，而我們往往會(huì)遇到一些平面統(tǒng)計(jì)問(wèn)題和空間統(tǒng)計(jì)問(wèn)題。因此我們需要推廣線段樹，使它變成能解決平面問(wèn)題的“矩形樹”和能解決空間問(wèn)題的“方塊樹”。將一維線段樹改成二維線段樹，有兩種方法。一種就是給原來(lái)線段樹中的每個(gè)結(jié)點(diǎn)都加多一棵線段樹，即“樹中有樹”。如下圖： 例如在主線段樹的結(jié)點(diǎn)1,3中，線段3,5表示的就是矩形(1,3,3,5) 注：本文用(x1,y1,x2,y2)表示左下角頂點(diǎn)坐標(biāo)為(x1,y1),右上角頂點(diǎn)坐標(biāo)為(x2,y2)的矩形。容易算出，用這種方法構(gòu)造一棵矩形(x1,y1,x2,y2)的線段樹需要的空間為,即空間復(fù)雜度為，其中Long_x，Long_y分別表示矩形的長(zhǎng)和寬。相應(yīng)地，時(shí)間復(fù)雜度為。其中n為操作數(shù)。由于這種線段樹有兩層，處理起來(lái)較麻煩。 另一種方式是直接將原來(lái)線段樹結(jié)點(diǎn)中的線段變成矩形。即每個(gè)結(jié)點(diǎn)代表一個(gè)矩形。因此矩形樹用的是四分的思想，每個(gè)矩形分割為4個(gè)子矩形。矩形(x1,y1,x2,y2)的4個(gè)兒子分別為(x1,y1,)、(,y1,x2,)、(x1,y2)、(,x2,y2) 例如下圖就是一棵以矩形(1,1,4,3)為根的矩形樹：易知，以(x1,y1,x2,y2)為根的矩形樹的空間復(fù)雜度也是。但由于它只有一層，處理起來(lái)比第一種方法方便。而且在這種矩形樹中，標(biāo)記思想依然適用。而第一種方法中，標(biāo)號(hào)思想在主線段樹上并不適用，只能在第二層線段樹上使用。但是這種方法的時(shí)間復(fù)雜度可能會(huì)達(dá)到。比起第一種來(lái)就差了不少。對(duì)于多維的問(wèn)題，第一種方法幾乎不可能使用。因此我們可以仿照第二種方法。例如對(duì)于n維的問(wèn)題。我們構(gòu)造以(a1,a2,a3,.,an,b1,b2,b3,.,bn)為根的線段樹，其中(a1,a2,a3.,an)表示的是左下角的坐標(biāo)，(b1,b2,b3,.,bn)表示的是右上角的坐標(biāo)。構(gòu)造的時(shí)候用的就不是二分，四分了，而是2n分，構(gòu)造出一棵2n叉樹。結(jié)點(diǎn)的個(gè)數(shù)變?yōu)?n(b1-a1)(b2-a2)(bn-an)。2.7 線段樹小結(jié) 作為解決統(tǒng)計(jì)類問(wèn)題的利器，線段樹在改進(jìn)和推廣之后，做到了高效地解決更多的問(wèn)題。因其適用范圍廣和實(shí)現(xiàn)上的方便，線段樹不失為一個(gè)優(yōu)秀的方法。但線段樹還是有一些缺陷的，下文將在與矩形切割進(jìn)行比較的時(shí)候提及。三、矩形切割矩形切割是一種處理平面上矩形的統(tǒng)計(jì)的方法。許多統(tǒng)計(jì)類的問(wèn)題通過(guò)數(shù)學(xué)建模后都能轉(zhuǎn)化為用矩形切割來(lái)解決。矩形切割的原型是線段切割。我們先來(lái)看看線段切割的思想。3.1 線段切割用回例1做例子。但是條件改變一下，就是涂色不一定是涂一種顏色，而是可以涂多種顏色，同一線段上后涂的顏色會(huì)覆蓋先涂的顏色。對(duì)每一種顏色都求出含有該種顏色的單位線段的條數(shù)。題目要我們對(duì)每種顏色都求出被覆蓋的單位線段的數(shù)目。如果所有的線段都是互不重疊的，那么我們只需把線段集合中同種顏色的所有線段的長(zhǎng)度累加，就能得出該種顏色被覆蓋的單位線段的數(shù)目了。但事實(shí)上線段之間會(huì)出現(xiàn)重疊的情況，因此我們引入線段切割的方法來(lái)對(duì)線段集合中的線段進(jìn)行動(dòng)態(tài)維護(hù)，使得所有線段兩兩不重疊。那么最后只需直接將線段的長(zhǎng)度累加，就能得出答案。其實(shí)線段切割的思想很簡(jiǎn)單。若線段集合中本來(lái)有一根線段a,b，現(xiàn)在加入一根新線段c,d。那么它們之間的位置關(guān)系可能有以下幾種：對(duì)于每一種位置關(guān)系，我們都可以通過(guò)切割線段a,b，并刪除某些小段（因?yàn)檫@些小段已被c,d覆蓋了），使得它與新線段c,d不重疊。因此，當(dāng)我們每次插入一條線段，就跟線段集合中的每一條線段a,b都判斷一下是否出現(xiàn)重疊，若出現(xiàn)重疊則對(duì)a,b進(jìn)行切割。判斷重疊的方法為：若ad或者cb，就不出現(xiàn)重疊，否則重疊。切割的方法就是：取線段a,b，c,d的交集k1,k2。若ak1，則加入線段a,k1；若k2=d)or(c=.b) then Cross false Else Cross trueEnd3.1.3 切割線段的過(guò)程Procedure Cut(Num,c,d)Begin If LineNum.ac then Add(LineNum.a,c) If dLineNum.b then Add(d,LineNum.b) Delete(Num);End其中Add過(guò)程是將一條線段加到線段集合中的過(guò)程：Procedure Add(a,b)Begin tot tot + 1 Linetot.a aLinetot.b bEnd 其中delete過(guò)程是將一條線段刪除的過(guò)程，可將線段集合中最后的一條線段移到要?jiǎng)h除線段的位置上完成刪除：Procedure Delete(Num)Begin LineNum Linetot tot tot -1End 根據(jù)線段切割的思想，我們稍做推廣，便能得出矩形切割的方法。3.2 矩形切割類似地，若矩形集合中已有矩形(x1,y1,x2,y2)，現(xiàn)加入矩形(x3,y3,x4,y4)。它們的位置關(guān)系可以有很多種（有17種之多），這里就不一一列舉了。但無(wú)論它們的位置關(guān)系如何復(fù)雜，運(yùn)用線段切割的思想來(lái)進(jìn)行矩形切割，就會(huì)變得十分明了。 我們將矩形的切割正交分解，先進(jìn)行x方向上的切割，再進(jìn)行y方向的切割。 以下圖為例：插入矩形(x3,y3,x4,y4)后，對(duì)矩形(x1,y1,x2,y2)進(jìn)行切割。Step 1:首先從x方向上切。把線段(x1,x2)切成(x1,x3)，(x4,x2)兩條線段。于是相應(yīng)地，我們就把兩個(gè)矩形切了出來(lái)(x1,y1,x3,y2)，(x4,y1,x2,y2)。把它們加到矩形集合中。去掉了這兩個(gè)矩形后，我們要切的矩形就變?yōu)?x3,y1,x4,y2)。Step 2:接著我們?cè)龠M(jìn)行y方向上的切割。把線段(y1,y2)切成(y1,y3)。相應(yīng)地又得到一個(gè)矩形(x3,y1,x4,y2)。把它放入矩形集合。Step 3:剩下的矩形為(x3,y3,x4,y2)，這個(gè)矩形已經(jīng)被矩形(x3,y3,x4,y4)覆蓋了，因此直接把它刪掉。 我們可以歸納出矩形切割的思想： 1、先對(duì)被切割矩形進(jìn)行x方向上的切割。取(x1,x2)，(x3,x4)的交集(k1,k2) 若x1k1，則加入矩形(x1,y1,k1,y2) 若k2x2，則加入矩形(k2,y1,x2,y2) 2、再對(duì)切剩的矩形(k1,y1,k2,y2) 進(jìn)行y方向上的切割。取(y1,y2)，(y3,y4)的交集(k3,k4) 若y1k3，則加入矩形(k1,y1,k2,k3) 若k4y2，則加入矩形(k1,k4,k2,y2) 3、把矩形(x1,y1,x2,y2)從矩形集合中刪除。切割過(guò)程的代碼如下：Procedure Cut(x1,y1,x2,y2,Direction)Var k1,k2Begin Case Direction of 1:Begin k1 Max(x1,x3) 計(jì)算線段(x1,x2)，(x3,x4)交集的左邊界 k2 Min(x2,x4) 計(jì)算線段(x1,x2)，(x3,x4)交集的右邊界 if x1k1 then Add(x1,y1,k1,y2) if k2x2 then Add(k2,y1,x2,y2) Cut(k1,y1,k2,y2,Direction+1) End 2:Begin k1 Max(y1,y3) k2 Min(y2,y4) if y1k1 then Add(x1,y1,x2,k1) if k2y2 then Add(x1,k2,x2,y2) End EndEnd 其中Add是加入矩形的過(guò)程。3.3 矩形切割的推廣本著矩形切割的思想，我們可以把矩形切割推廣為立方體切割，甚至推廣到n維空間中的切割。兩個(gè)n維物體有重疊部分的充要條件就是它們?cè)趎個(gè)方向上都存在交集。就是說(shuō)(x1,x2)和(x3,x4)有交集；(y1,y2)和(y3,y4)有交集；。切割的方法也是類似的：先在x方向上切，然后在y方向上切，接著在z方向上切，一直到在第n個(gè)方向上切。 當(dāng)n變大的時(shí)候，如果用這種方法來(lái)寫程序，將會(huì)顯得很復(fù)雜，甚至變得不可能。我們可以做些改動(dòng)來(lái)簡(jiǎn)化代碼，將一個(gè)n維“物體”用兩個(gè)數(shù)組表示出來(lái)(a1,a2,a3,an,b1,b2,b3,bn)。然后相應(yīng)地改動(dòng)一下Add過(guò)程，就可以不用分類討論，直接改成一重循環(huán)，只需幾行就能完成。由于比較簡(jiǎn)單，這里就不寫出來(lái)了。例3衛(wèi)星覆蓋 NOI 97 第二試第三題衛(wèi)星可以覆蓋空間直角坐標(biāo)系中一定大小的立方體空間，衛(wèi)星處于該立方體的中心。其中(x,y,z)為立方體的中心點(diǎn)坐標(biāo)，r為此中心點(diǎn)到立方體各個(gè)面的距離（即r為立方體高的一半）。立方體的各條邊均平行于相應(yīng)的坐標(biāo)軸。我們可以用一個(gè)四元組(x,y,z,r)描述一顆衛(wèi)星的狀態(tài)，它所能覆蓋的空間體積。由于一顆衛(wèi)星所能覆蓋的空間體積是有限的，因此空間中可能有若干顆衛(wèi)星協(xié)同工作。它們所覆蓋的空間區(qū)域可能有重疊的地方，如下圖所示（陰影部分表示重疊的區(qū)域）。寫一個(gè)程序，根據(jù)給定的衛(wèi)星分布情況，計(jì)算它們所覆蓋的總體積。輸入輸出輸入文件是Cover.in。文件的第一行是一個(gè)正整數(shù)N（1=N=10O）：表示空間中的衛(wèi)星總數(shù)。接下來(lái)的N行每行給出了一顆衛(wèi)星的狀態(tài)，用空格隔開的四個(gè)正整數(shù)x,y,z,r依次表示了該衛(wèi)星所能覆蓋的立方體空間的中心點(diǎn)坐標(biāo)和半高，其中-1000=x,y,z=1000, 1=r=200。 輸出文件是Cover.out。文件只有一行,包括一個(gè)正整數(shù)，表示所有這些衛(wèi)星所覆蓋的空間總體積。樣例Cover.in30 0 0 31 1 0 119 3 5 6Cover.out1944 這題可以用立方體切割來(lái)做，思想也是一樣，每讀入一個(gè)立方體(x3,y3,z3,x4,y4,z4)，就和已有的立方體(x1,y1,z1,x2,y2,z2)判斷是否有重疊，有的話就進(jìn)行切割。所有的數(shù)據(jù)處理完后就可以將全部立方體的體積加起來(lái)，就能得出答案了。 應(yīng)該注意的是新切割生成的立方體與立方體(x3,y3,z3,x4,y4,z4)是不會(huì)有重疊部分的。因此我們?cè)谧x入矩形(x3,y3,z3,x4,y4,z4)之前，先把當(dāng)前立方體集合中的立方體總數(shù)tot記錄起來(lái) tot1 tot，那么循環(huán)判斷立方體重疊只需循環(huán)到tot1就行了，新生成的立方體就無(wú)需與立方體(x3,y3,z3,x4,y4,z4)判斷是否重疊了。這樣可以節(jié)省不少時(shí)間。具體細(xì)節(jié)就不說(shuō)了，程序參見附錄3.4 矩形切割的應(yīng)用 如果我們引入矩形切割單單就是為了切矩形，那就沒(méi)多大意義了，畢竟這樣的題目不多見。其實(shí)矩形切割作為一個(gè)數(shù)學(xué)模型，常常可以在許多統(tǒng)計(jì)類的問(wèn)題中使用。例如下面這題：例4War Field Statistical System NOI2003前OIBH某次網(wǎng)上比賽試題 2050年，人類與外星人之間的戰(zhàn)爭(zhēng)已趨于白熱化。就在這時(shí)，人類發(fā)明出一種超級(jí)武器，這種武器能夠同時(shí)對(duì)相鄰的多個(gè)目標(biāo)進(jìn)行攻擊。凡是防御力小于或等于這種武器攻擊力的外星人遭到它的攻擊，就會(huì)被消滅。然而，擁有超級(jí)武器是遠(yuǎn)遠(yuǎn)不夠的，人們還需要一個(gè)戰(zhàn)地統(tǒng)計(jì)系統(tǒng)時(shí)刻反饋外星人部隊(duì)的信息。這個(gè)艱巨的任務(wù)落在你的身上。請(qǐng)你盡快設(shè)計(jì)出這樣一套系統(tǒng)。這套系統(tǒng)需要具備能夠處理如下2類信息的能力： 1、外星人向x1，x2內(nèi)的每個(gè)位置增援一支防御力為v的部隊(duì)。 2、人類使用超級(jí)武器對(duì)x1，x2內(nèi)的所有位置進(jìn)行一次攻擊力為v的打擊。系統(tǒng)需要返回在這次攻擊中被消滅的外星人個(gè)數(shù)。（注：防御力為i的外星人部隊(duì)由i個(gè)外星人組成，其中第j個(gè)外星人的防御力為j。）輸入格式 從文件War.in第一行讀入n，m。其中n表示有n個(gè)位置，m表示有m條信息。以下有m行，每行有4個(gè)整數(shù)k，x1，x2，v用來(lái)描述一條信息 。k表示這條信息屬于第k類。x1，x2，v為相應(yīng)信息的參數(shù)。k=1 or 2。 注：你可以認(rèn)為最初的所有位置都沒(méi)有外星人存在。 規(guī)模：0n=30000；0x1=x2=n；0v=30000；0m=2000輸出格式 結(jié)果輸出到文件War.out。按順序輸出需要返回的信息。輸入樣例 對(duì)應(yīng)輸出3 5 無(wú)1 1 3 4 無(wú)2 1 2 3 61 1 2 2 無(wú)1 2 3 1 無(wú)2 2 3 5 9輸出樣例69 這道題看上去與矩形切割好像并無(wú)多大關(guān)系。但仔細(xì)分析一下，這題可以轉(zhuǎn)化為用矩形切割模型來(lái)解決。每次向x1,x2增添一支防御力為v的部隊(duì)，因?yàn)槊恐Х烙関的部隊(duì)是由v個(gè)外星人組成的，防御力依次為1,2,3，,v。如果我們?cè)谄矫嬷苯亲鴺?biāo)系上來(lái)表示這種操作，則有：若在位置2,6上增加一支防御力為3的部隊(duì)，那么情況就如右圖所示，其實(shí)等于加入了一個(gè)矩形(1,0,6,3)。因此在x1,x2上增添一支防御力為v的部隊(duì)就等于增添一個(gè)矩形(x1-1,0,x2,v)。同理，在x1,x2上使用攻擊力為v的武器，就等于把與矩形(x1-1,0,x2,v)有重疊部分的矩形都進(jìn)行切割。所以這道題就變成了簡(jiǎn)單的矩形切割問(wèn)題。 由于這道題要我們求的是每次使用武器所殺死的外星人數(shù)目。因此我們可以相應(yīng)地根據(jù)這個(gè)改動(dòng)一下做法。在增加部隊(duì)，即插入矩形(x3,y3,x4,y4)的時(shí)候，并不需要與矩形集合中的矩形(x1,y1,x2,y2)判斷是否重疊，因?yàn)閷?duì)于這道題來(lái)說(shuō)，重疊是沒(méi)有關(guān)系的（一個(gè)格子可以站多個(gè)具有同樣防御力的外星人）。而在使用武器的時(shí)候，我們像往常一樣切割矩形，只是順便做做統(tǒng)計(jì)罷了。程序請(qǐng)參見附錄。 由此我們可以看到，矩形切割并不是只是局限于解決幾何類的問(wèn)題，只要我們將題目數(shù)學(xué)建模后能運(yùn)用矩形切割的思想，那么矩形切割也不失為一個(gè)好方法。四、線段樹與矩形切割的比較 同為解決動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題利刃的線段樹與矩形切割，區(qū)別不少。為了更快捷，更完美地解決問(wèn)題，什么時(shí)候使用線段樹較好，什么時(shí)候使用矩形切割更優(yōu)，的確值得我們研究研究。 對(duì)兩種方法進(jìn)行比較，我們可以先從復(fù)雜度入手，畢竟這個(gè)要素是我們決定是否使用一種方法的決定性因素。4.1 線段樹的時(shí)空復(fù)雜度線段樹的時(shí)空復(fù)雜度在前面已經(jīng)做了介紹。4.1.1 線段樹的空間復(fù)雜度1. 線段樹的空間復(fù)雜度是，其中Long_x為最長(zhǎng)線段的長(zhǎng)度。2. 二維線段樹是，其中Long_x，Long_y分別為最大矩形的長(zhǎng)、寬。3. 三維線段樹是，其中Long_x，Long_y，Long_z分別為最大方塊的長(zhǎng)、寬、高。4.1.2 線段樹的時(shí)間復(fù)雜度1. 線段樹的時(shí)間復(fù)雜度是。2. 二維線段樹是。3. 三維線段樹是。4.2矩形切割的時(shí)空復(fù)雜度 矩形切割的時(shí)間復(fù)雜度是較淺顯的。我們每次讀入一個(gè)矩形，就必須跟矩形集合中的所有矩形進(jìn)行比較，看看是否出現(xiàn)重疊。因此時(shí)間復(fù)雜度是O(m*n)。其中m表示數(shù)據(jù)中的矩形數(shù)目，n表示矩形集合中矩形數(shù)目。然而矩形集合中的矩形數(shù)目是會(huì)改變的，n應(yīng)該是矩形集合中矩形數(shù)目的峰值（即曾經(jīng)在矩形集合中出現(xiàn)的矩形數(shù)目的最大值）。關(guān)于該峰值n的計(jì)算，就是計(jì)算空間復(fù)雜度的問(wèn)題了。 4.2.1矩形切割的空間復(fù)雜度 矩形切割的空間復(fù)雜度是由峰值n決定的，最多會(huì)出現(xiàn)多少個(gè)矩形，我們就開多大的數(shù)組。而n的計(jì)算卻十分困難。因?yàn)樵谄矫鎯?nèi)放置矩形的情況不一樣，切割出來(lái)的矩形個(gè)數(shù)和狀況也就會(huì)不同。為此，我們可以先做一些數(shù)據(jù)，數(shù)據(jù)中的矩形是隨機(jī)生成的?？纯串?dāng)數(shù)據(jù)中的矩形個(gè)數(shù)為m的時(shí)候，峰值n究竟會(huì)是多少。請(qǐng)看下表：表1矩形數(shù)m100500100050001000050000100000峰值n2394796801015129617412092這些數(shù)據(jù)中的矩形是隨機(jī)生成的。其中m是輸入數(shù)據(jù)中的矩形個(gè)數(shù)。對(duì)于數(shù)據(jù)中的每個(gè)矩形(x1,y1,x2,y2)都有：0=x1x2=60000，0=y1y2=60000。其中對(duì)矩形集合中矩形數(shù)目的峰值n，計(jì)算方法是：對(duì)同一個(gè)m值，生成10組數(shù)據(jù)，得出10個(gè)n值。取這些結(jié)果的平均值作為n的值。 在矩形個(gè)數(shù)較小的時(shí)候，如m=100，峰值n達(dá)到了239，是m的兩倍多。但隨著m增大的加快，峰值n的增加卻比較緩慢。在m=5000時(shí)，n1015。m=10000時(shí)，n=1296。相差不多?？梢妌與m并非是正比關(guān)系。也就是說(shuō)，即使矩形個(gè)數(shù)猛增，矩形集合中矩形數(shù)目的最大值只是維持在一個(gè)較低的水平。因此對(duì)隨機(jī)數(shù)據(jù)而言，空間復(fù)雜度是很小的。 然而這僅僅是對(duì)于隨機(jī)數(shù)據(jù)。究竟在構(gòu)造出來(lái)的數(shù)據(jù)中，峰值n可以達(dá)到多少呢？我們嘗試構(gòu)造這樣的一種數(shù)據(jù)： 數(shù)據(jù)一共有m個(gè)矩形。前k個(gè)矩形如此放置：第一個(gè)矩形(1,1,x,y)是最大的。（其中應(yīng)使x,y的值足夠大，例如x=y=100000000）。以后的每一個(gè)矩形都比前一個(gè)矩形縮小一點(diǎn)點(diǎn)。即如果前一個(gè)矩形是(x1,y1,x2,y2)，則下一個(gè)矩形為(x1+1,y1+1,x2-1,y2-1)。例如第2個(gè)矩形就是(2,2,x-1,y-1)，第3個(gè)矩形就是(3,3,x-2,y-2)。由于后一個(gè)矩形被前一個(gè)矩形完全覆蓋，且沒(méi)有邊重疊，因此第t+1個(gè)矩形會(huì)將第t個(gè)矩形切割成4塊。放入k個(gè)矩形之后，就有4*(k-1)+14k-3個(gè)矩形了。例如圖1就是k=4時(shí)的情況，共有13個(gè)矩形。之后的m-k個(gè)矩形如此放置：因?yàn)榍懊鎘個(gè)矩形中最后一個(gè)矩形是(k,k,x-k,y-k)，所以現(xiàn)在放一些這樣的矩形：(k+1,0,k+2,y+1)，(k+3,0,k+4,y+1)，(k+5,0,k+6,y+1)，。如圖2所示。每放置這樣的一個(gè)矩形，就會(huì)與2k-1個(gè)矩形產(chǎn)生重疊，切割后多出2k-1個(gè)矩形。又因?yàn)槲覀兎胖玫谝粋€(gè)矩形(1,1,x,y)的時(shí)候已假設(shè)x,y足夠大，因此后m-k個(gè)矩形都能與2k-1個(gè)矩形發(fā)生重疊。因此會(huì)多出個(gè)矩形。加上先前的4k-3個(gè)矩形一共是個(gè)矩形。利用二次函數(shù)求最值可知當(dāng)時(shí)函數(shù)取到最大值?？臻g復(fù)雜度達(dá)到了！這樣的復(fù)雜度顯然是致命的。 可見，如果針對(duì)矩形切割算法的弱點(diǎn)刻意構(gòu)造數(shù)據(jù)，復(fù)雜度將高到無(wú)法承受。如果并非針對(duì)性地構(gòu)造極端數(shù)據(jù)，由表1的結(jié)果可以看出矩形切割還是很優(yōu)秀的。4.2.2 矩形切割的時(shí)間復(fù)雜度 知道了矩形切割的空間復(fù)雜度，時(shí)間復(fù)雜度就好辦了。前面已經(jīng)說(shuō)了，時(shí)間復(fù)雜度是。根據(jù)表1，若是隨機(jī)數(shù)據(jù)。在m10000的時(shí)候，n=1296。還是可以接受的。而當(dāng)m=50000時(shí)，n=1741，就十分勉強(qiáng)了。而對(duì)于極端數(shù)據(jù)。時(shí)間復(fù)雜度是，在500個(gè)矩形的時(shí)候就已經(jīng)需要1億多次的運(yùn)算，效率是很低的。4.3 線段樹與矩形切割適用范圍的比較 根據(jù)線段樹和矩形切割的復(fù)雜度。我們就可以思考出它們的適用范圍。 線段樹的空間復(fù)雜度是固定的，即。若其中的Long_x很大，即線段的端點(diǎn)取值范圍很大，線段樹的空間復(fù)雜度將會(huì)十分大甚至無(wú)法承受。特別是在矩形樹和方塊樹中。例如方塊的長(zhǎng)寬高限定在1000以下?？臻g復(fù)雜度就已經(jīng)達(dá)到了8*109。根本無(wú)法承受。相對(duì)來(lái)說(shuō)，矩形切割在這方面就十分有優(yōu)勢(shì)了。它存儲(chǔ)一個(gè)矩形只需4個(gè)域，一個(gè)方塊也只需6個(gè)域，完全不受Long_x,Long_y等邊界的限制。矩形有多大對(duì)矩形切割的復(fù)雜度是沒(méi)有影響的。例如例3中的邊界范圍限制-1000=x,y,z=1000和例4中的0n=30000；0x1=x2=n；0v=30000都決定了線段樹是無(wú)法承受這種空間復(fù)雜度的。而對(duì)于矩形切割來(lái)說(shuō)卻是不在話下。 線段樹的時(shí)間復(fù)雜度很小，只有，因此對(duì)于操作數(shù)較多的題目線段樹可以做到得心應(yīng)手，效率很高。然而操作數(shù)一多，矩形切割的效率就不高了。而例3中立方體的數(shù)目最多才100個(gè)，因此就這題而言用矩形切割來(lái)做就顯得十分優(yōu)秀了。 在編程復(fù)雜度上，線段樹和矩形切割都是很容易就能實(shí)現(xiàn)的。 因此我們可以得出結(jié)論：對(duì)邊界范圍小，操作數(shù)多的題目，我們選擇線段樹；對(duì)邊界范圍大，操作數(shù)少的題目，我們選擇矩形切割。五、總結(jié)到此，我們已較深入地了解到線段樹和矩形切割的方方面面。經(jīng)過(guò)對(duì)它們的思想，基本操作，改進(jìn)和推廣等方面的思考與研究，我們更清晰地體會(huì)到了這兩把解決統(tǒng)計(jì)問(wèn)題的利刃。在對(duì)它們進(jìn)行復(fù)雜度，優(yōu)缺點(diǎn)，適用范圍等各方面的比較的過(guò)程中，我們總結(jié)出了什么時(shí)候該用哪個(gè)方法，積累了一定的經(jīng)驗(yàn)，也為以后更好地解決該類問(wèn)題打下了一定的基礎(chǔ)。畢竟文章篇幅有限，本文也只是僅僅介紹了兩個(gè)方法，涉及的范圍并不廣。但我想，發(fā)現(xiàn)和提出問(wèn)題，思考并解決問(wèn)題這種能力是無(wú)論在哪個(gè)領(lǐng)域哪個(gè)方面都應(yīng)該提倡的。若本文能在為大家介紹了兩種方法的同時(shí)，也能引起大家對(duì)這一方面的重視，激發(fā)大家對(duì)統(tǒng)計(jì)類問(wèn)題更深入的研究和對(duì)其它問(wèn)題更廣泛的思考，我的目的就達(dá)到了?！緟⒖嘉墨I(xiàn)】1、NOI97試題2、OIBH網(wǎng)上比賽試題【附錄】附錄1：例1的線段樹程序 Sample1.pasProgram Sample1;Const Maxn=120000; 最多支持120000條線段，即支持Long_x=60000Type TreeNode=Record a,b,Left,Right:Longint; Cover,bj:shortint; 記錄線段是否被覆蓋；線段的標(biāo)記 End;Var i,j,k,m,n,tot,c,d,Ans:longint; Tree:array0.Maxn of TreeNode;Procedure MakeTree(a,b:Longint); 建立線段樹的過(guò)程Var Now:longint;Begin inc(tot); Now:=tot; TreeNow.a:=a; TreeNow.b:=b; if a+1b then begin TreeNow.Left:=tot+1; MakeTree(a,(a+b) shr 1); TreeNow.Right:=tot+1; MakeTree(a+b) shr 1,