線段樹及其應(yīng)用

線段樹及其應(yīng)用

劉汝佳

目錄

-線段樹的定義

?動(dòng)態(tài)統(tǒng)計(jì)問題I

?動(dòng)態(tài)統(tǒng)計(jì)問題II

?動(dòng)態(tài)統(tǒng)計(jì)問題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

和應(yīng)用相關(guān)的幾個(gè)小問題

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

?一樣大

?原始線段長(zhǎng)度不是2的哥:允許不平均分割還是補(bǔ)

齊到2的哥？

?（允許不平均分割）

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

?（是單個(gè)元素）

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

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

?分割合并都可以

性質(zhì)

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

?任兩個(gè)結(jié)點(diǎn)要么是包含關(guān)系要么沒有公共

部分，不可能部分重疊

-給定一個(gè)葉子P,從根到P路徑上所有結(jié)點(diǎn)

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

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

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

210g2L條不相交線段的并

基本算法

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

89

線段樹的關(guān)鍵

?用線段樹解題的關(guān)鍵

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

-設(shè)計(jì)區(qū)間附加信息和維護(hù)/統(tǒng)計(jì)算法

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

一個(gè)序關(guān)系

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

半點(diǎn)含糊！

■建議：先設(shè)計(jì)便于解題的附加信息，如果難

以維護(hù)就加以修改

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

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

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

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

?附加信息:s(p)表示結(jié)點(diǎn)p所代表區(qū)間內(nèi)所有

元素之和

?維護(hù)算法

-ADD:給i對(duì)應(yīng)結(jié)點(diǎn)的所有直系祖先s值增加k

-SUM:做區(qū)間分解,把對(duì)應(yīng)結(jié)點(diǎn)的s值相加

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

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

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

-QUERY(i):求A[i]

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

-QUERY(i)就是讀取i對(duì)應(yīng)的結(jié)點(diǎn)上的s值

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

所有結(jié)點(diǎn)都需要修改！

?需要新的附加信息

新的附加信息

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

它們.等到需要計(jì)算的時(shí)候再說

?假設(shè)結(jié)點(diǎn)P對(duì)應(yīng)的區(qū)間是a(p)表示所有

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

-如果［I/不對(duì)應(yīng)任何結(jié)點(diǎn)怎么辦？區(qū)間分解！

-這樣的信息實(shí)質(zhì)上是把所有ADD指令合并到了

一起.可以嗎？可以的，因?yàn)锳DD具有疊加性

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

A［i］的增加量

繼續(xù)討論

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

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

-但在同一條指令中被增加的結(jié)點(diǎn)卻不能都被修

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

-正確的理解是:先把指令A(yù)DD分解為不超過

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

單一的結(jié)點(diǎn)與之對(duì)應(yīng),然后每條原子ADD操作

只修改該結(jié)點(diǎn)本身的計(jì)數(shù)器

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

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

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

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

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

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

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

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

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

SUM的實(shí)現(xiàn)

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

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

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

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

ADD操作影響到它

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

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

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

SUM的計(jì)算

右圖表示影響

SUM(7,9)的所

有區(qū)間

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

[5,9],[7,9]

-影響部分：7,

[8,9],8,9

完整的算法

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

一再附加一個(gè)sa(p),表示以p為根的子樹所有結(jié)點(diǎn)

的a值之前

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

還要沿途修改sa值

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

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

?兩個(gè)操作均為O(logn)

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

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

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

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

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

信息：m(p)表示結(jié)點(diǎn)p所代表區(qū)間內(nèi)所有元

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

做,但MODIFY呢？

遞推法

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

路徑上所有m值，但關(guān)鍵是:如何修改？

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

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

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

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

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

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

?保證：自底向上遞推

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

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

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

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

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

的總長(zhǎng)度)

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

-(保證存在)

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

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

覆蓋長(zhǎng)度可以維護(hù)么？

?考慮根結(jié)點(diǎn).如果c(root)>0,則整個(gè)區(qū)間都

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

據(jù)左右兒子遞推

?是否可以定義l(p),表示結(jié)點(diǎn)p對(duì)應(yīng)的區(qū)間內(nèi)

被覆蓋到的總長(zhǎng)度呢？不可以！

-初始為空時(shí)進(jìn)行Add(1,n),則樹中所有結(jié)點(diǎn)對(duì)

應(yīng)的l(p)都應(yīng)被修改！

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

新的維護(hù)信息

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

作在p對(duì)應(yīng)的區(qū)間中覆蓋了多大長(zhǎng)度，則

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

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

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

護(hù)即可

例題1.火星地圖

?2051年，科學(xué)家們探索出了火星上

n(nv=10000)個(gè)不同的矩形(坐標(biāo)為不超過

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

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

繪制出火星的完整地圖。

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

大的面積，你能幫助他們寫一個(gè)程序計(jì)算

出結(jié)果嗎？

分析

?水平離散化

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

?時(shí)間復(fù)雜度：O(nlogn)

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

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

?實(shí)現(xiàn)兩個(gè)操作

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

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

分析

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

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

間內(nèi)元素排序好的序列

?查詢Query(iJ,k)

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

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

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

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

分析

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

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

的數(shù)logn

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

-總時(shí)間：logW*log2n

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

每個(gè)節(jié)點(diǎn)內(nèi)的排序數(shù)組.空間:O(nlogn)

分析

-有修改的情形:每個(gè)結(jié)點(diǎn)不能用有序表了，

而需要是一棵平衡樹

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

間為O(log2n)

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

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

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

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

應(yīng)依次輸出“4,3"、”5,2”

分析

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

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

所屬于的連通塊編號(hào)

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

為0(n)(對(duì)交界線進(jìn)行合并操作，修改內(nèi)

部連通塊個(gè)數(shù))

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

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

時(shí)間復(fù)雜度為O(nlogn)

例題4.01矩陣

?給n*n的01矩