線段樹及其應用

線段樹及其應用

劉汝佳

目錄

-線段樹的定義

?動態(tài)統(tǒng)計問題I

?動態(tài)統(tǒng)計問題II

?動態(tài)統(tǒng)計問題III

線段樹的定義

?線段［1,9］的線段樹和［2,8］的分解

R23456780[%9]

[123生678gl[1,4]

Z\

7

|1|2|3|4|56|789]9]

|1|2|3|4|5|6|7|8

可1234567[859]

扇89

和應用相關的幾個小問題

-線段長度為偶數(shù):左小右大還是左大右小

?一樣大

?原始線段長度不是2的哥:允許不平均分割還是補

齊到2的哥？

?（允許不平均分割）

?葉子是單個元素i還是單位線段[i,i+1]?

?（是單個元素）

?靜態(tài)。r動態(tài)?（靜態(tài)）

?建立：自頂向下遞歸分割還是自底向上合并？

?分割合并都可以

性質

?每層都是［a,b］的劃分.記L:b-a,則共logzL層

?任兩個結點要么是包含關系要么沒有公共

部分，不可能部分重疊

-給定一個葉子P,從根到P路徑上所有結點

（即P的所有直系祖先）代表的區(qū)間都包含點

P,且其他結點代表的區(qū)間都不包含點P

?給定一個區(qū)間［I,r］,可以把它分解為不超過

210g2L條不相交線段的并

基本算法

?找點：根據(jù)定義，從根一直走到葉子logL

89

線段樹的關鍵

?用線段樹解題的關鍵

-得到討論區(qū)間（可能要先離散化）

-設計區(qū)間附加信息和維護/統(tǒng)計算法

?線段樹自身沒有任何數(shù)據(jù)，不像BST一樣有

一個序關系

?警告:想清楚附加信息的準確含義，不能有

半點含糊！

■建議：先設計便于解題的附加信息，如果難

以維護就加以修改

問題1.動態(tài)統(tǒng)計問題I

?包含n個元素的數(shù)組A

-ADD(i,k):設A[i]=A[i]+k

-SUM(p,q):求A[p]+A[p+1]+…+A[q]

?附加信息:s(p)表示結點p所代表區(qū)間內所有

元素之和

?維護算法

-ADD:給i對應結點的所有直系祖先s值增加k

-SUM:做區(qū)間分解,把對應結點的s值相加

問題2.動態(tài)統(tǒng)計問題II

?包含n個元素的數(shù)組A

-ADD(i,j,k):^A[i],A[i+1],...A[j]均增加k

-QUERY(i):求A[i]

?先看看是否可以沿用剛才的附加信息

-QUERY(i)就是讀取i對應的結點上的s值

-ADD呢？極端情況下，如果是修改整個區(qū)間，則

所有結點都需要修改！

?需要新的附加信息

新的附加信息

?Lazy思想：記錄有哪些指令，而不真正執(zhí)行

它們.等到需要計算的時候再說

?假設結點P對應的區(qū)間是a(p)表示所有

形如ADD(i,j,k)的所有k之和

-如果［I/不對應任何結點怎么辦？區(qū)間分解！

-這樣的信息實質上是把所有ADD指令合并到了

一起.可以嗎？可以的，因為ADD具有疊加性

?QUERY:把所有直系祖先的a值相加，就是

A［i］的增加量

繼續(xù)討論

?附加信息a(p)到底是什么？

-首先要在同一條指令中被增加

-但在同一條指令中被增加的結點卻不能都被修

改否則ADD(1,n)仍然要修改所有結點

-正確的理解是:先把指令ADD分解為不超過

210g2L條指令,每條指令的區(qū)間［i,j］都在樹中有

單一的結點與之對應,然后每條原子ADD操作

只修改該結點本身的計數(shù)器

問題3.動態(tài)統(tǒng)計問題III

?包含n個元素的數(shù)組A

-ADD(i,j,k):給A[i],A[i+1],.?.A[j]均增加k

-SUM(p,q):求A[p]+A[p+1]+…+A[q]

?顯然動態(tài)統(tǒng)計問題I和II都是它的特殊情況

-問題I中,ADD操作的i二j

-問題II中，SUM操作的p二q

?由于ADD操作和問題II一樣，這里沿用它的

ADD實現(xiàn),那SUM怎么辦？

SUM的實現(xiàn)

?前面曾經(jīng)提到，區(qū)間統(tǒng)計的一般做法是把查

詢區(qū)間進行分解，一一統(tǒng)計然后加起來

?在本題中，需要計算每個原子區(qū)間的數(shù)之

和.它們的和是多少呢？這取決于有多少

ADD操作影響到它

?回憶:任何兩個樹中區(qū)間要么相互包含要么

沒有公共部分.因此影響一個原子區(qū)間的

ADD操作都是它的直接祖先和后代

SUM的計算

右圖表示影響

SUM(7,9)的所

有區(qū)間

-影響全部:[1,9],

[5,9],[7,9]

-影響部分：7,

[8,9],8,9

完整的算法

-至此，算法輪廓已經(jīng)出來

一再附加一個sa(p),表示以p為根的子樹所有結點

的a值之前

-ADD:區(qū)間分解后除了修改各原子區(qū)間的a值外,

還要沿途修改sa值

-SUM:在區(qū)間分解的同時統(tǒng)計經(jīng)過的a值,然后

把原子區(qū)間的sa值累加進來

?兩個操作均為O(logn)

問題4.動態(tài)區(qū)間最小值

?包含n個元素的數(shù)組A

-MODIFY(iJ):設A[i]=j

-MIN(p,q):求min{A[p],A[p+1A[q]}

?和動態(tài)統(tǒng)計問題I很類似，因此考慮設計附加

信息：m(p)表示結點p所代表區(qū)間內所有元

素的最小值，那么MIN仍可以通過區(qū)間分解

做,但MODIFY呢？

遞推法

?MODIFY操作仍然只需要修改從根到葉子的一條

路徑上所有m值，但關鍵是:如何修改？

?回憶：動態(tài)統(tǒng)計問題I中，區(qū)間［l,j］中任何一個元素

增加了k,則區(qū)間綜合增加k.但最小值呢？只根據(jù)

原來的m(p)自身無法計算出新的m(p)

?方法：遞推.設p的兒子為I和r,則

m(p)=min{m(l),m(r)}

?前提：計算m(p)時m⑴和m(r)已經(jīng)算出.

?保證：自底向上遞推

問題5.區(qū)間并的長度

?實現(xiàn)一個區(qū)間集合

-Add(x,y):增加區(qū)間［x,y］(1<=x<y<=n)

-Delete(x,y):刪除區(qū)間［x,y］

-Total:區(qū)間并的長度(即被至少一個區(qū)間覆蓋到

的總長度)

-約定:刪除的區(qū)間［x,y］一定是以前插入過

-(保證存在)

?增加區(qū)間時進行分解，設置計數(shù)器c(p),表示

分解后指令Add(x,y)的條數(shù)

覆蓋長度可以維護么？

?考慮根結點.如果c(root)>0,則整個區(qū)間都

被覆蓋，返回L,但如果c(root)=0呢？需要根

據(jù)左右兒子遞推

?是否可以定義l(p),表示結點p對應的區(qū)間內

被覆蓋到的總長度呢？不可以！

-初始為空時進行Add(1,n),則樹中所有結點對

應的l(p)都應被修改！

-怎么辦？修改l(p)的定義

新的維護信息

?設l(p)表示以p為根的子樹中的所有Add操

作在p對應的區(qū)間中覆蓋了多大長度，則

Add(1,n)只需要修改根

?每個原子區(qū)間的插入、刪除都只影響它的

直接祖先,插入/刪除后自底向上用遞推法維

護即可

例題1.火星地圖

?2051年，科學家們探索出了火星上

n(nv=10000)個不同的矩形(坐標為不超過

109的正整數(shù))區(qū)域并繪制了這些局部的地

圖，如圖所示。波羅的海太空研究所希望

繪制出火星的完整地圖。

?科學家們首先需要知道這些矩形共占了多

大的面積，你能幫助他們寫一個程序計算

出結果嗎？

分析

?水平離散化

?從左到右掃描,利用”區(qū)間并的長度”

?時間復雜度：O(nlogn)

例題2.動態(tài)區(qū)間k大數(shù)

,維護一個數(shù)組A[1...n]

?實現(xiàn)兩個操作

-Modify(i.j),設A[i]=j

-Query(ij,k),返回第k大元素

分析

?首先考慮沒有修改的情形

?預處理：建立線段樹，每個線段保存該區(qū)

間內元素排序好的序列

?查詢Query(iJ,k)

-把［ij］進行區(qū)間分解

-二分W,每次統(tǒng)計這些區(qū)間內一共有多少個數(shù)

比W大，用logW次統(tǒng)計可求出第k大元素

?如何統(tǒng)計原子區(qū)間內比W大的元素總個數(shù)?

分析

?統(tǒng)計原子區(qū)間內一共有多少個數(shù)比w大

-區(qū)間內的數(shù)已排序，用二分每個區(qū)間求比W大

的數(shù)logn

-累加所有2logn個區(qū)間比W大的數(shù)，共log2n

-總時間：logW*log2n

?實現(xiàn):一個歸并排序可以同時構造線段樹和

每個節(jié)點內的排序數(shù)組.空間:O(nlogn)

分析

-有修改的情形:每個結點不能用有序表了，

而需要是一棵平衡樹

?每次Modify需要修改O(logn)棵平衡樹，總時

間為O(log2n)

例題3,動態(tài)連通塊

-給出n*n棋盤，有黑有白.每次改變其中一個格

子顏色，輸出黑白連通塊的個數(shù)

?左圖，翻轉(3,2)和(2,3)后分別得到中圖和右圖,

應依次輸出“4,3"、”5,2”

分析

?對行集合建立線段樹，區(qū)間［i,j］保存內部的

黑白連通塊個數(shù)以及第i行和第j行每個格子

所屬于的連通塊編號

?由［i,mid］和［mid+1,j］可以合并成為時間

為0(n)(對交界線進行合并操作，修改內

部連通塊個數(shù))

?根據(jù)指令(x,y)所在行修改葉子區(qū)間，并往上

遞推。最多修改logn個區(qū)間，因此每次操作

時間復雜度為O(nlogn)

例題4.01矩陣

?給n*n的01矩