線段樹(shù)的應(yīng)用

線段樹(shù)的應(yīng)用引例數(shù)列操作假設(shè)有一列數(shù){Ai}(1≤i≤n)，支持如下兩種操作：將Ak的值加D?！瞜,D是輸入的數(shù)〕輸出As+As+1+…+At。〔s,t都是輸入的數(shù)，S≤T〕

輸入：第一行一個(gè)整數(shù)n，第二行為n個(gè)整數(shù)，表示{Ai}的初始值。第三行為一個(gè)整數(shù)m，表示操作數(shù)下接m行，每行描述一個(gè)操作，有如下兩種情況：ADDkd(表示將Ak加d，1<=k<=n，d為整數(shù))SUMst〔表示輸出As+…+At〕輸出：對(duì)于每一個(gè)SUM提問(wèn)，輸出結(jié)果如果按題目要求直接模擬：每一個(gè)ADD操作的復(fù)雜度是O(1)每一個(gè)SUM操作的復(fù)雜度是O(N)可見(jiàn)對(duì)于M次SUM詢問(wèn)，復(fù)雜度是O(NM)有沒(méi)有更好的方法呢？這里我們提出一種稱之為線段樹(shù)的數(shù)據(jù)結(jié)構(gòu)。引例數(shù)列操作引例線段樹(shù)的定義線段樹(shù)是一棵二叉樹(shù)，記為T(a,b)，參數(shù)a,b表示區(qū)間[a,b]，其中b-a稱為區(qū)間的長(zhǎng)度，記為L(zhǎng)。線段樹(shù)T(a,b)也可遞歸定義為：假設(shè)L>1:[a,(a+b)div2]為T的左兒子；[(a+b)div2,b]為T的右兒子。假設(shè)L=1:T為葉子節(jié)點(diǎn)。表示區(qū)間[1,10]的線段樹(shù)樣例：

[1,10]

[1,5]

[5,10]

[1,3]

[3,5]

[5,7]

[7,10]

[1,2]

[2,3]

[3,4]

[4,5]

[5,6]

[6,7]

[7,8]

[8,10]

[8,9]

[9,10]

引例線段樹(shù)的建立我們知道，對(duì)于長(zhǎng)度為n的線段建立的線段樹(shù)，至多只有nlogn個(gè)節(jié)點(diǎn)，故建立線段樹(shù)的復(fù)雜度是O(nlogn)ProcedureMakeTree(a,b)VarNow:LongintBegintot←tot+1Now←totTree[Now].a←aTree[Now].b←bIfa+1<bthen

Tree[Now].Left←tot+1MakeTree(a,)Tree[Now].Right←tot+1MakeTree(,b)End

引例回到原問(wèn)題我們用線段樹(shù)來(lái)維護(hù)序列。給線段樹(shù)的每個(gè)節(jié)點(diǎn)增加一個(gè)域Tree[i].S，表示該區(qū)間內(nèi)所有值的和。對(duì)于ADDkd操作，只需要從根節(jié)點(diǎn)開(kāi)始遍歷線段樹(shù)中每個(gè)包含了k的區(qū)間節(jié)點(diǎn)，然后修改S域。由于這樣的區(qū)間至多只有l(wèi)ogn個(gè)，所以一次ADD操作的復(fù)雜度是O(logn)引例SUM操作對(duì)于待計(jì)算的區(qū)間[s,t]：Functiongetsum(v):integer;if(s<=Tree[v].a)and(Tree[v].b<=t)thengetsum:=Tree[v].Selsebegintot:=0;if[s,t]和Tree[v].Left表示的區(qū)間相交thentot:=tot+getsum(Tree[v].Left);if[s,t]和Tree[v].Right表示的區(qū)間相交thentot:=tot+getsum(Tree[v].Right);getsum:=totend;我們不難發(fā)現(xiàn)這個(gè)過(guò)程中所遍歷到的區(qū)間數(shù)〔節(jié)點(diǎn)數(shù)〕和線段樹(shù)的深度同階，因此時(shí)間復(fù)雜度是O(logn)引例問(wèn)題的解決綜上，M次操作的時(shí)間復(fù)雜度為O(Mlogn)通過(guò)引入線段樹(shù)的數(shù)據(jù)結(jié)構(gòu)，雖然ADD操作的復(fù)雜度提高到了O(logn)。但SUM操作變得更快(O(logn))。從而也使得算法在大數(shù)據(jù)處理上更加高效。例一Picture(IOI98)墻上貼了一些矩形的張貼畫和照片。他們的邊都是垂直或者水平的。每個(gè)矩形可以局部后者全部被其他的矩形覆蓋。把這些矩形看作一個(gè)整體，他們的邊界長(zhǎng)度就是他們的輪廓長(zhǎng)度。所有頂點(diǎn)坐標(biāo)都是整數(shù)。任務(wù)：寫一個(gè)程序計(jì)算輪廓長(zhǎng)度。下面的圖1是一個(gè)7個(gè)矩形的例子：圖1：七個(gè)矩形這些矩形的輪廓如圖2所示圖2：圖1中7個(gè)矩形的輪廓例一Picture(IOI98)預(yù)處理：如右圖所示，用2n條橫線與2n條縱線將坐標(biāo)平面重新進(jìn)行劃分。定義新的坐標(biāo)軸，并記錄每一個(gè)“元線段〞的長(zhǎng)度。這樣就只剩下了2n*2n個(gè)坐標(biāo)點(diǎn)，便于今后的計(jì)算。離散化，將2n條矩形的橫邊和2n條縱邊取出來(lái)，分別計(jì)算例一Picture(IOI98)做完預(yù)處理之后，如果直接計(jì)算，不難想到O(n2)的算法。事實(shí)上，利用線段樹(shù)我們可以設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度為O(nlogn)的高效算法。在分析算法之前，我們先來(lái)看看線段樹(shù)上插入和刪除線段的操作。例一線段樹(shù)的插入、刪除(1)增加一個(gè)Tree[i].Cover域，記錄該區(qū)間〔線段〕被覆蓋的次數(shù)。那么在線段樹(shù)中插入線段[c,d]的代碼段如下：ProcedureInsert(v)Begin

If(c<Tree[v].a)and(Tree[v].b<d)then

Tree[v].Cover←Tree[v].Cover+1

ElseIfc<thenInsert(Tree[v].Left)Ifd>thenInsert(Tree[v].Right)End例一線段樹(shù)的插入、刪除(2)刪除線段[c,d]的操作，只需要將Tree[v].Cover←Tree[v].Cover+1改成Tree[v].Cover←Tree[v].Cover–1即可。與引例中計(jì)算SUM的過(guò)程段類似地分析，不難得到線段樹(shù)中插入和刪除線段的時(shí)間復(fù)雜度都是O(logn)例一Picture(IOI98)回到原問(wèn)題，首先我們考慮縱向的離散區(qū)間。我們從左到右依次掃描每個(gè)離散區(qū)間。如上，考察第一個(gè)離散區(qū)間。藍(lán)色的線段顯然要算入最后的“輪廓長(zhǎng)度〞。我們把藍(lán)色線段插入線段樹(shù)。例一Picture(IOI98)在第二個(gè)區(qū)間我們參加了另一個(gè)矩形的左邊界，如右圖藍(lán)色線段。把這條線段參加到線段樹(shù)中。但是用圓形圈起來(lái)的局部不應(yīng)該算到“輪廓長(zhǎng)度〞里面去。究其原因，因?yàn)閳A形圈起來(lái)的局部和之前已經(jīng)插入的線段重合了。也就是說(shuō)每插入一條新線段，只有不和之前已插入線段重合的局部才應(yīng)該被算到“輪廓長(zhǎng)度〞里面去。接著考察第三個(gè)區(qū)間，我們面對(duì)的是一個(gè)矩形的右邊界，因此我們要把它對(duì)應(yīng)的綠色線段從樹(shù)中刪除。右圖的藍(lán)色線段中，圓形圈起來(lái)的局部不算到輪廓里面去。究其原因，是因?yàn)檫@個(gè)局部和除被刪除線段之外的線段有交集。例一Picture(IOI98)例一Picture(IOI98)綜合前面的分析，我們得到：每次插入/刪除操作之前，線段樹(shù)中線段覆蓋的總長(zhǎng)度是X；之后的總長(zhǎng)度是Y。那么應(yīng)該算入輪廓的長(zhǎng)度就是|X-Y|。關(guān)于如何計(jì)算“覆蓋的總長(zhǎng)度〞，與引例中計(jì)算區(qū)間和類似，這里不再贅述。這樣我們就可以通過(guò)一遍掃描，計(jì)算出所有的縱向輪廓長(zhǎng)度。這是只需要把圖旋轉(zhuǎn)90度，就可以用同樣的方法計(jì)算橫向輪廓的長(zhǎng)度了。例一Picture(IOI98)由于每條矩形的邊界線段只被掃描一遍，而且掃描的時(shí)候進(jìn)行的插入或刪除操作的時(shí)間復(fù)雜度是O(logn)所以算法的總時(shí)間復(fù)雜度是O(nlogn)。例二Square給你一個(gè)n*n的方格棋盤，初始時(shí)每個(gè)格子都是白色。現(xiàn)在要刷M次黑色或白色的油漆。每次刷漆的區(qū)域都是一個(gè)平行棋盤邊緣的矩形區(qū)域。輸入n,M,以及每次刷漆的區(qū)域和顏色，輸出刷了M次之后棋盤上還有多少個(gè)棋格是白色。例二一維問(wèn)題首先我們從簡(jiǎn)單入手，考慮一維的問(wèn)題。即對(duì)于一個(gè)長(zhǎng)度為n的白色線段，對(duì)它進(jìn)行M次修改〔每次更新某一子區(qū)域的顏色〕。問(wèn)最后還剩下的白色區(qū)域有多長(zhǎng)。對(duì)于這個(gè)問(wèn)題，很容易想到建立一棵線段樹(shù)的模型。例二一維問(wèn)題的解決對(duì)于這個(gè)問(wèn)題，在線段樹(shù)中增添一個(gè)域Tree[v].white，記錄該區(qū)間當(dāng)前有多少局部是白色。然后再進(jìn)行線段的插入和顏色統(tǒng)計(jì)。單次操作的復(fù)雜度都是O(logn)算法的總時(shí)間復(fù)雜度是O(Mlogn)例二Square那么原來(lái)的問(wèn)題怎么解決呢？為了適應(yīng)原問(wèn)題的特殊性，我們需要把線段樹(shù)進(jìn)行調(diào)整，即首先在橫坐標(biāo)上建立線段樹(shù)，它的每個(gè)節(jié)點(diǎn)是一棵建立在縱坐標(biāo)上的線段樹(shù)〔即樹(shù)中有樹(shù)〕