線段樹及其應用

《線段樹及其應用》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、線段樹及其應用引例數(shù)列操作假設有一列數(shù){Ai}(1≤i≤n)，支持如下兩種操作：將Ak的值加D。（k,D是輸入的數(shù)）輸出As+As+1+…+At。（s,t都是輸入的數(shù)，S≤T）輸入：第一行一個整數(shù)n，第二行為n個整數(shù)，表示{Ai}的初始值。第三行為一個整數(shù)m，表示操作數(shù)下接m行，每行描述一個操作，有如下兩種情況：ADDkd(表示將Ak加d，1<=k<=n，d為整數(shù))SUMst（表示輸出As+…+At）輸出：對于每一個SUM提問，輸出結果如果按題目要求直接模擬：每一個ADD操作的復雜度是O(1)每一個SUM操作的復雜度是O(N)可見對于M次SUM詢問，復雜度是O(NM

2、)有沒有更好的方法呢？這里我們提出一種稱之為線段樹的數(shù)據(jù)結構。引例數(shù)列操作引例線段樹的定義線段樹是一棵二叉樹，記為T(a,b)，參數(shù)a,b表示區(qū)間[a,b]，其中b-a稱為區(qū)間的長度，記為L。線段樹T(a,b)也可遞歸定義為：若L>1:[a,(a+b)div2]為T的左兒子；[(a+b)div2,b]為T的右兒子。若L=1:T為葉子節(jié)點。表示區(qū)間[1,10]的線段樹樣例：[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]引例線段樹的建立我

3、們知道，對于長度為n的線段建立的線段樹，至多只有nlogn個節(jié)點，故建立線段樹的復雜度是O(nlogn)ProcedureMakeTree(a,b)VarNow:LongintBegintot←tot+1Now←totTree[Now].a←aTree[Now].b←bIfa+1

4、開始遍歷線段樹中每個包含了k的區(qū)間節(jié)點，然后修改S域。由于這樣的區(qū)間至多只有l(wèi)ogn個，所以一次ADD操作的復雜度是O(logn)引例SUM操作對于待計算的區(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+ge

5、tsum(Tree[v].Right);getsum:=totend;我們不難發(fā)現(xiàn)這個過程中所遍歷到的區(qū)間數(shù)（節(jié)點數(shù)）和線段樹的深度同階，因此時間復雜度是O(logn)引例問題的解決綜上，M次操作的時間復雜度為O(Mlogn)通過引入線段樹的數(shù)據(jù)結構，雖然ADD操作的復雜度提高到了O(logn)。但SUM操作變得更快(O(logn))。從而也使得算法在大數(shù)據(jù)處理上更加高效。例一Picture(IOI98)墻上貼了一些矩形的張貼畫和照片。他們的邊都是垂直或者水平的。每個矩形可以部分后者全部被其他的矩形覆蓋。把這些矩形看作一個整體，他們的邊界長度就是他們的輪廓長度。所有

6、頂點坐標都是整數(shù)。任務：寫一個程序計算輪廓長度。下面的圖1是一個7個矩形的例子：圖1：七個矩形這些矩形的輪廓如圖2所示圖2：圖1中7個矩形的輪廓例一Picture(IOI98)預處理：如右圖所示，用2n條橫線與2n條縱線將坐標平面重新進行劃分。定義新的坐標軸，并記錄每一個“元線段”的長度。這樣就只剩下了2n*2n個坐標點，便于今后的計算。離散化，將2n條矩形的橫邊和2n條縱邊取出來，分別計算例一Picture(IOI98)做完預處理之后，如果直接計算，不難想到O(n2)的算法。事實上，利用線段樹我們可以設計出一個時間復雜度為O(nlogn)的高效算法。在分析算法之前

7、，我們先來看看線段樹上插入和刪除線段的操作。例一線段樹的插入、刪除(1)增加一個Tree[i].Cover域，記錄該區(qū)間（線段）被覆蓋的次數(shù)。則在線段樹中插入線段[c,d]的代碼段如下：ProcedureInsert(v)BeginIf(cthenInsert(Tree[v].Right)End例一線段樹的插入、刪除(2)刪除線段[c,d]的操作，只需要將Tree[v].C