?

參考資料：

　　[1]:ACM線段樹的區(qū)間合并（圖文）?[提取碼：o380]

　　[2]:博客

?

首先讓我們來(lái)看這個(gè)問(wèn)題：

• 給出一個(gè)序列，由 0和1 組成
• 給出一個(gè)區(qū)間 [ l , r ]
• 求這個(gè)區(qū)間中只包含1的子串的最大長(zhǎng)度

我們可以使用一下解法：

• 區(qū)間 DP : 時(shí)間復(fù)雜度O(n³)的預(yù)處理，O(n¹)的詢問(wèn)
• 胡亂預(yù)處理+詢問(wèn)O(n²)

但是如果增加新的條件呢？

• 給出a,b，要求將第a位的值改為b
• 剛才給出的解法都是依靠預(yù)處理來(lái)達(dá)到之后的詢問(wèn)時(shí)間的
• 如果我們要做修改操作，就要重新預(yù)處理

聯(lián)想線段樹的作用，他剛好可以處理區(qū)間查詢，更新問(wèn)題

• 如果我們能夠使用線段樹來(lái)解決這類區(qū)間查詢問(wèn)題（但并不是簡(jiǎn)單的帶修改求和或RMQ）
• 我們可以達(dá)到詢問(wèn)的O(logn和查詢的O(logn)
• 線段樹的建造是O(nlogn)，查詢的總時(shí)間就是O(nlogn)
• 即使不帶修改也要比前面的方法優(yōu)秀

解決這類問(wèn)題，線段樹由固定的套路

• 這類問(wèn)題基本是“帶修改的區(qū)間查詢”“連續(xù)”問(wèn)題
• 他可以問(wèn)你一個(gè)區(qū)間的LCIS或者是一個(gè)區(qū)間的連續(xù)某數(shù)字等等

那么，介紹了線段樹區(qū)間更新的功能后，開始回歸正題，如何使用？

　　如圖所示，是由"1101111011"構(gòu)造的一顆線段樹，要求某區(qū)間連續(xù)的1的個(gè)數(shù)（一部分，都畫出來(lái)太麻煩了，主要是用于方便理解概念用的）

　　

　　在此之前，先聲明一下我的代碼風(fēng)格：

1 #define ls(x) (x<<1)//左兒子 2 #define rs(x) (x<<1|1)//右兒子 3 4 struct SegmentTree 5 { 6 int l,r; 7 int lsum,rsum; 8 int sum; 9 int mark;//懶惰標(biāo)記 10 int mid() 11 { 12 return l+((r-l)>>1); 13 } 14 int len() 15 { 16 return r-l+1; 17 } 18 }segTree[4*maxn];

　　①首先介紹一下相關(guān)概念

　　　　lsum :?從本節(jié)點(diǎn)區(qū)間最左端開始（向右）一共有l(wèi)sum個(gè)連續(xù)的1;(segTree[1].lsum = 2)

　　　　rsum :?從本節(jié)點(diǎn)區(qū)間最右端開始（向左）一共有rsum個(gè)連續(xù)的1;(segTree[1].rsum = 2)

　　　　sum :?本區(qū)間一共最多有 sum 個(gè)連續(xù)的1;(segTree[1].sum = 4)

　　　　mark : 區(qū)間更新的懶惰標(biāo)記，比如，如果將區(qū)間[l,r]中所有的1變?yōu)?，那么 mark = 0 就意味著要將此區(qū)間中的所有1變?yōu)?;

　　②如何求解lsum,rsum,sum ? 下面介紹函數(shù)pushUp(int pos)的作用

　　　　pushUp(int pos) : 把當(dāng)前pos結(jié)點(diǎn)的"左右兒子的節(jié)點(diǎn)"信息更新到pos結(jié)點(diǎn);

　　　　例如，假設(shè)求出 1號(hào)節(jié)點(diǎn)"1101111011"的左右兒子節(jié)點(diǎn)的lsum,rsum,sum，那么便可通過(guò)pushUp(1)來(lái)求出1號(hào)節(jié)點(diǎn)的lsum,rsum,sum值；

　　　　segTree[1].lsum = segTree[ls(1)].lsum;

　　　　segTree[1].rsum = segTree[rs(1)].rsum;

　　　　這兩個(gè)操作是毋庸置疑的，1號(hào)節(jié)點(diǎn)的lsum至少為ls(1)號(hào)節(jié)點(diǎn)的lsum，但有沒有可能比 segTree[ls(1)].lsum 大呢？

　　　　答案是肯定的，如果 segTree[ls(1)].lsum = segTree[ls(1)].len()，那么

　　　　segTree[1].lsum = segTree[ls(1)].lsum + segTree[rs(1)].rsum;

　　　　如上圖，如果將1號(hào)節(jié)點(diǎn)的左兒子中的'0'改為'1'，那么segTree[1].lsum = 5+2 = 7;

　　　　segTree[1].rsum 同理；

　　　　那segTree[1].sum 該如何求呢？

　　　　很顯然，它等于 （左兒子的sum值，右兒子的sum值，左兒子的rsum+右兒子的lsum值）的最大值；

　　　　pushUp()函數(shù)代碼如下：

1 //返回三者最大值 2 int Max(int a,int b,int c) 3 { 4 return max(max(a,b),c); 5 } 6 void pushUp(int pos) 7 { 8 segTree[pos].lsum=segTree[ls(pos)].lsum; 9 segTree[pos].rsum=segTree[rs(pos)].rsum; 10 11 //判斷是否可以增加 12 if(segTree[pos].lsum == segTree[ls(pos)].len()) 13 segTree[pos].lsum += segTree[rs(pos)].lsum; 14 if(segTree[pos].rsum == segTree[rs(pos)].len()) 15 segTree[pos].rsum += segTree[ls(pos)].rsum; 16 17 segTree[pos].sum=Max(segTree[ls(pos)].sum, 18 segTree[rs(pos)].sum, 19 segTree[ls(pos)].rsum+segTree[rs(pos)].lsum); 20 }

　　③介紹完pushUp(int pos)函數(shù)后，下面來(lái)介紹pushDown(int pos)函數(shù)的作用

　　　　pushDown(int pos) : 把當(dāng)前pos結(jié)點(diǎn)的信息傳遞給兒子結(jié)點(diǎn)

　　　　還記得區(qū)間更新懶惰標(biāo)記中的pushDown(int pos)函數(shù)嗎？

　　　　之所以能夠正確求解，就是這個(gè)函數(shù)的作用，在區(qū)間更新，查詢操作中，每來(lái)到一個(gè)大區(qū)間，都要將這個(gè)區(qū)間的

　　　　懶惰標(biāo)記向下傳遞，這樣才不至于出錯(cuò)。

　　　　那么線段樹區(qū)間合并中的pushDown(int pos)的作用也差不多；

　　　　假設(shè)有兩種操作

　　　　1.將區(qū)間[l,r]全變?yōu)?#39;0'；

　　　　2.將區(qū)間[l,r]全變?yōu)?#39;1'；

　　　　那么，相應(yīng)的，mark就需要有三個(gè)取值：

　　　　mark = -1 : 不做任何操作；

　　　　mark = ?1 :?將區(qū)間[l,r]全變?yōu)?#39;1'；

　　　　mark = ?0 :?將區(qū)間[l,r]全變?yōu)?#39;0'；

　　　　如果segTree[pos].mark = 1，那么在向下傳遞標(biāo)記的時(shí)候，左右兒子的lsum,rsum,sum分別全都變?yōu)閟egTree[ls(pos)].len(),segTree[rs(pos)].len();

　　　　如果segTree[pos].mark = 0，那么在向下傳遞標(biāo)記的時(shí)候，左右兒子的lsum,rsum,sum全都變?yōu)?

　　　　pushDown(int pos)代碼如下：

1 void F(int pos,int val) 2 { 3 segTree[pos].lsum=val; 4 segTree[pos].rsum=val; 5 segTree[pos].sum=val; 6 } 7 /** 8 mark=-1 : no operator 9 mark= 1 : 0變成1 10 mark= 0 : 1變成0 11 */ 12 void pushDown(int pos) 13 { 14 int &mark=segTree[pos].mark; 15 if(mark == -1) 16 return ; 17 segTree[ls(pos)].mark=mark; 18 segTree[rs(pos)].mark=mark; 19 if(mark == 0) 20 { 21 F(ls(pos),0); 22 F(rs(pos),0); 23 } 24 else 25 { 26 F(ls(pos),segTree[ls(pos)].len()); 27 F(rs(pos),segTree[rs(pos)].len()); 28 } 29 mark=-1; 30 }

　　④介紹完主要的pushUp(),pushDown()后，建樹，查詢，更新操作就比較簡(jiǎn)單了，具體細(xì)節(jié)看代碼

?

?

?

　　

轉(zhuǎn)載于:https://www.cnblogs.com/violet-acmer/articles/10519956.html

總結(jié)

以上是生活随笔為你收集整理的线段树区间合并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。