第三篇線段樹(shù)了——重點(diǎn)不在于解決題目，通過(guò)題目理解線段樹(shù)才是重點(diǎn)
前面寫(xiě)了一篇關(guān)于線段樹(shù)的單點(diǎn)更新壹粟，線段樹(shù)的單點(diǎn)更新就只要找到指定的葉節(jié)點(diǎn)并進(jìn)行更新即可宿百，這篇文章主要根據(jù)相關(guān)例題講下關(guān)于線段樹(shù)的區(qū)間更新
例題
題意
N個(gè)氣球排成一排垦页，共有N條指令，每條指令表示從a-->b每個(gè)氣球涂一次顏色盏袄，問(wèn)所有指令執(zhí)行完之后宋光，各個(gè)氣球依次被涂過(guò)多少次顏色炭菌。
導(dǎo)學(xué)
首先回顧一下線段樹(shù)的單點(diǎn)更新
void add(int k,int p,int value){
if(tree[p].left==k&&tree[p].right==k){ //如果找到了對(duì)應(yīng)位置的葉子節(jié)點(diǎn)，就進(jìn)行增加操作
tree[p].value+=value;
return;
}
int mid=(tree[p].left+tree[p].right)/2; //從子節(jié)點(diǎn)中尋找
if(k<=mid) add(k,p*2,value);
else add(k,p*2+1,value);
tree[p].value = tree[2*p].value+tree[2*p+1].value; //子節(jié)點(diǎn)更新了赘艳，父節(jié)點(diǎn)也要更新
}
單點(diǎn)更新就相當(dāng)于范圍是[a,a]克握，然后因?yàn)楸囟ㄓ星覂H有一個(gè)節(jié)點(diǎn)和這個(gè)范圍相同（葉節(jié)點(diǎn)）菩暗，所以就是不斷的向左子樹(shù)或者右子樹(shù)中找，找到這個(gè)葉節(jié)點(diǎn)之后旷坦，就進(jìn)行相應(yīng)的修改操作。修改完成之后旗芬，需要相應(yīng)修改其父節(jié)點(diǎn)的值
那相對(duì)應(yīng)的捆蜀，區(qū)間更新的更新范圍是[a,b]，不管這個(gè)[a,b]是否和某一節(jié)點(diǎn)的范圍吻合誊薄，至少一定存在這幾個(gè)節(jié)點(diǎn)锰茉，范圍相加就等于[a,b]。那是不是把這幾個(gè)節(jié)點(diǎn)更新就好了呢咐刨？求每個(gè)氣球被涂過(guò)多少次顏色又怎么實(shí)現(xiàn)呢扬霜？
解析
我們?cè)趯?shí)現(xiàn)代碼之后著瓶，發(fā)現(xiàn)，區(qū)間更新與單點(diǎn)更新的代碼很相似
void add(int l,int r,int p){
if(tree[p].left==l&&tree[p].right==r){
tree[p].value++; //在父節(jié)點(diǎn)上更新沸久，子節(jié)點(diǎn)不做處理
return;
}
int mid=(tree[p].left+tree[p].right)/2;
if(r<=mid) add(l,r,2*p); //向左子樹(shù)更新
else if(l>mid) add(l,r,2*p+1); //向右子樹(shù)更新
else{ //左右子樹(shù)同時(shí)更新
add(l,mid,2*p);
add(mid+1,r,2*p+1);
}
}
相比較而言余蟹，單點(diǎn)更新是更新葉節(jié)點(diǎn)，然后返回時(shí)順帶更新葉節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)窑睁。而區(qū)間更新只更新到父節(jié)點(diǎn)葵孤，子節(jié)點(diǎn)不做處理尤仍，當(dāng)然如果父節(jié)點(diǎn)覆蓋不了，就會(huì)細(xì)化到相應(yīng)的子節(jié)點(diǎn)中苏遥。
那么查詢呢？
通過(guò)上面的更新的步驟我們發(fā)現(xiàn)惕耕。假設(shè)整個(gè)線段樹(shù)的范圍是[0,10]诫肠，那么根節(jié)點(diǎn)的左子樹(shù)的范圍是[0,5]，右子樹(shù)的范圍是[6,10]挤安。假設(shè)第一次更新區(qū)間是[0,5]丧鸯，第二次更新的區(qū)間是[5,10]丛肢。
第一次修改，會(huì)將根節(jié)點(diǎn)的左子樹(shù)更新次數(shù)+1穆刻，第二次修改會(huì)將葉節(jié)點(diǎn)[5,5]和根節(jié)點(diǎn)的右子樹(shù)更新次數(shù)+1（因?yàn)闆](méi)有[5,10]范圍的節(jié)點(diǎn)杠步，只有[5,5]+[6,10]）
當(dāng)我們需要知道第5個(gè)氣球被涂了幾次的時(shí)候，我們從根節(jié)點(diǎn)開(kāi)始找[5,5]這個(gè)葉節(jié)點(diǎn)朵锣，發(fā)現(xiàn)父節(jié)點(diǎn)[0,5]被涂了甸私，我們將sum+=value（value是父節(jié)點(diǎn)被涂的次數(shù)颠蕴，在上面的假設(shè)中，就是1），然后以此類推往下外冀，直到到達(dá)葉節(jié)點(diǎn)[5,5]為止雪隧。
所以總結(jié)一下就是员舵，更新只更新父節(jié)點(diǎn)（最大覆蓋單位）藕畔，如果父節(jié)點(diǎn)不夠更新再依次細(xì)化。在統(tǒng)計(jì)每個(gè)點(diǎn)時(shí)韭邓，從根節(jié)點(diǎn)開(kāi)始遍歷計(jì)算女淑，遇到父節(jié)點(diǎn)有更新的就相應(yīng)增加（因?yàn)楦腹?jié)點(diǎn)更新了辜御，就說(shuō)明該父節(jié)點(diǎn)覆蓋的所有子節(jié)點(diǎn)都需要更新），然后最后求得的就是該葉節(jié)點(diǎn)的總更新次數(shù)
AC代碼（下面還有拓展~）
#include <iostream>
#include <stdio.h>
#define M 100005
using namespace std;
struct node{
int left;
int right;
int value;
}tree[M*4];
int sum=0;
void build_tree(int l,int r,int p){
tree[p].left=l;
tree[p].right=r;
tree[p].value=0;
if(l==r) return;
int mid=(l+r)/2;
build_tree(l,mid,2*p);
build_tree(mid+1,r,2*p+1);
}
void add(int l,int r,int p){
if(tree[p].left==l&&tree[p].right==r){
tree[p].value++;
return;
}
int mid=(tree[p].left+tree[p].right)/2;
if(r<=mid) add(l,r,2*p);
else if(l>mid) add(l,r,2*p+1);
else{
add(l,mid,2*p);
add(mid+1,r,2*p+1);
}
}
void search(int k,int p){
sum+=tree[p].value;
if(tree[p].left==k&&tree[p].right==k) return;
int mid=(tree[p].left+tree[p].right)/2;
if(k<=mid) search(k,2*p);
else search(k,2*p+1);
}
int main(){
int n,i,num1,num2;
while(cin>>n&&n!=0){
build_tree(1,n,1);
for(i=0;i<n;i++){
scanf("%d%d",&num1,&num2);
add(num1,num2,1);
}
for(i=1;i<n;i++){
sum=0;
search(i,1);
cout<<sum<<" ";
}
sum=0;
search(n,1);
cout<<sum<<endl;
}
return 0;
}
拓展
題意
這是道英文題，簡(jiǎn)單的描述一下題意瓣窄。還是拿糖果舉例把纳鼎，桌上有n堆糖果，初始數(shù)量每堆糖果都是1劝贸，然后會(huì)進(jìn)行一些類似于X Y Z的操作，每個(gè)操作都表示把從X堆到Y(jié)堆的糖果數(shù)量都變成Z逗宁。例如1 5 3就表示把第1映九、2、3瞎颗、4件甥、5堆糖果的數(shù)量都變成3。最后需要求的是所有糖果堆的總數(shù)量
思路
這題與上面講到的區(qū)間刷新不太一樣哼拔。上面那題是累加引有，所以第一次增加某一節(jié)點(diǎn)后，后續(xù)修改之后倦逐，就不需要改動(dòng)譬正。
舉個(gè)栗子，第一次修改[0,5]曾我，第二次修改[5,10]粉怕。
對(duì)于上面講到的區(qū)間刷新，第二次修改不需要去動(dòng)第一次修改的內(nèi)容抒巢，僅僅需要在葉節(jié)點(diǎn)上進(jìn)行附加贫贝，附加的結(jié)果就是葉節(jié)點(diǎn)更新次數(shù)+父節(jié)點(diǎn)([0,5])更新次數(shù)
而對(duì)于這題的區(qū)間更新，比如第一次將[0-5]修改成2蛉谜，第二次將[5,10]修改成3稚晚。那么第二次的修改直接導(dǎo)致的是第一次的修改部分無(wú)效，也就是說(shuō)悦陋，第二次修改之后蜈彼，[0-4]是被第一次修改的2，但是[5,5]已經(jīng)是3了俺驶，那么怎么把[0-5]這個(gè)父節(jié)點(diǎn)的標(biāo)記變成[0-4]就成了一個(gè)問(wèn)題幸逆。
解析
還是就代碼進(jìn)行解析
struct node{
int left,right,flag,value; //left和right表示的是范圍，value表示的是這個(gè)范圍的數(shù)值
}tree[M*4];
void build_tree(int l,int r,int p){
tree[p].left=l;
tree[p].right=r;
tree[p].value=0;
tree[p].flag=0; //懶惰標(biāo)記
if(l==r){
tree[p].value=1;
tree[p].flag=1; //葉節(jié)點(diǎn)的懶惰標(biāo)記都為1
return;
}
int mid=(tree[p].left+tree[p].right)/2;
build_tree(l,mid,p*2);
build_tree(mid+1,r,p*2+1);
}
……
cin>>n>>m;
build_tree(1,n,1);
不知道細(xì)心的你有沒(méi)有發(fā)現(xiàn)暮现，定義線段樹(shù)的結(jié)構(gòu)體中多了一個(gè)flag还绘，被稱為——懶惰標(biāo)記
那這個(gè)懶惰標(biāo)記是干嘛的呢？
首先我們看build_tree這個(gè)建樹(shù)操作栖袋。他把所有的父節(jié)點(diǎn)的value和懶惰標(biāo)記flag都置0拍顷，而葉節(jié)點(diǎn)的初始value就是題中給出的1，懶惰標(biāo)記flag也是1塘幅。其余和前面的建樹(shù)都一樣昔案，為什么要這么建樹(shù)，懶惰標(biāo)記是干嘛的呢电媳？
懶惰標(biāo)記
第一次更新了范圍[0,5]為2踏揣。懶惰標(biāo)記就跟程序說(shuō)，[0,5]這個(gè)范圍以下的所有子節(jié)點(diǎn)的值都是2匾乓，如果要統(tǒng)計(jì)總數(shù)了捞稿，到我這里就可以懶惰一下，不用往下再走了拼缝，我下面的所有數(shù)值之和就是(5-0)×2了娱局。但是程序你只有執(zhí)行到有懶惰標(biāo)記的地方才能停下，沒(méi)有懶惰標(biāo)記的地方咧七，即使value不為0也不能停衰齐！
是不是有點(diǎn)感覺(jué)到懶惰標(biāo)記的用法了，如果有思路猪叙，可以先試著獨(dú)立去完成下這道題~
然后看下一段代碼
void update(int l,int r,int p,int value){
if(tree[p].left==l&&tree[p].right==r){ //如果這個(gè)節(jié)點(diǎn)的范圍等于需要更新的范圍
tree[p].value=value; //更新值
tree[p].flag=1; //懶惰標(biāo)記置1
return;
}
//如果范圍不完全匹配
if(tree[p].flag==1){ //如果懶惰標(biāo)記已經(jīng)置1娇斩，就向下延伸仁卷，且當(dāng)前節(jié)點(diǎn)懶惰標(biāo)記清零
tree[p].flag=0;
tree[p*2].flag=1;
tree[p*2+1].flag=1;
tree[p*2].value=tree[p].value;
tree[p*2+1].value=tree[p].value;
}
int mid=(tree[p].left+tree[p].right)/2;
if(r<=mid) update(l,r,p*2,value);
else if(l>mid) update(l,r,p*2+1,value);
else{
update(l,mid,p*2,value);
update(mid+1,r,p*2+1,value);
}
}
類似的穴翩，更新操作也只是多了一段if判斷代碼犬第。如果范圍完全匹配，那沒(méi)話說(shuō)芒帕，修改value歉嗓，將懶惰標(biāo)記flag置1。但是在沒(méi)有完全匹配時(shí)背蟆，就需要進(jìn)行判斷了鉴分，如果當(dāng)前懶惰標(biāo)記為0，那相安無(wú)事~一旦發(fā)現(xiàn)當(dāng)前這個(gè)不完全匹配的節(jié)點(diǎn)懶惰標(biāo)記已經(jīng)置1了
就像上面說(shuō)的带膀，第一次將范圍[0,5]修改成2志珍，第二次將范圍[5,10]修改成3，那么在第二次修改的時(shí)候垛叨，由于最終目的地是葉節(jié)點(diǎn)[5,5]伦糯，所以會(huì)經(jīng)過(guò)[0,5]這個(gè)已經(jīng)被懶惰的節(jié)點(diǎn)。
每到達(dá)一個(gè)已經(jīng)被懶惰的節(jié)點(diǎn)嗽元，且范圍不匹配敛纲，那就需要把懶惰標(biāo)記分給子節(jié)點(diǎn)，比如[0,5]的子節(jié)點(diǎn)是[0,2]和[3,5]剂癌，那么就把[0,5]懶惰標(biāo)記清空淤翔，告訴程序，這個(gè)范圍更新的數(shù)據(jù)已經(jīng)無(wú)效了佩谷，但是因?yàn)閭鬟f給了子節(jié)點(diǎn)旁壮，所以[0,2]范圍的值是2還是有效的，但是[3,5]的范圍還是要被經(jīng)過(guò)谐檀，還是要被修改抡谐，依次類推。
到葉節(jié)點(diǎn)一定會(huì)停下稚补，因?yàn)槿~節(jié)點(diǎn)的懶惰標(biāo)記始終為1
void search(int l,int r,int p){
if(tree[p].left==l&&tree[p].right==r&&tree[p].flag==1){
sum=sum+(tree[p].right-tree[p].left+1)*tree[p].value;
return;
}
int mid=(tree[p].left+tree[p].right)/2;
if(r<=mid) search(l,r,p*2);
else if(l>mid) search(l,r,p*2+1);
else{
search(l,mid,p*2);
search(mid+1,r,p*2+1);
}
}
在計(jì)算總數(shù)的時(shí)候童叠，如果遇到父節(jié)點(diǎn)的懶惰標(biāo)記為1，那么直接增加整段父節(jié)點(diǎn)的值即可~
AC代碼
基本上面的分析代碼已經(jīng)都給出了课幕，AC代碼就不貼了厦坛，整合一下就行，畢竟重點(diǎn)還是理解
區(qū)間刷新乍惊，單點(diǎn)刷新以及其他的一些操作知識(shí)杜秸，都只是線段樹(shù)中的基本操作，比賽時(shí)很少會(huì)有這么裸的題润绎，后續(xù)會(huì)增加真題實(shí)戰(zhàn)撬碟，但是會(huì)發(fā)現(xiàn)把只要線段樹(shù)基礎(chǔ)操作理解了诞挨，這些真題也就迎刃而解了
