原文地址：http://blog.csdn.net/zip_fan/article/details/46775633

寫的很好，昨天剛剛開始寫線段樹，有些地方還不是很明白，看了這篇博文，學會了數組形式保存線段樹，還學會了區間更新

以下為轉載的博文內容

?

距離第一次接觸線段樹已經一年多了，再次參加ACM暑假集訓，這一次輪到我們這些老家伙們給學弟學妹們講解線段樹了，所以就自己重新把自己做過的題目看了一遍，然后寫篇博客紀念一下。作為一個菜鳥，文中肯定有很多表達不是很準確甚至錯誤的地方，歡迎各位大牛指正。

? ? ? ? 作為近年來算法競賽里面最火爆的數據結構考點，它的用法和問法層出不窮。而作為解決反復對區間的更新和查詢問題最好的數據結構，它擁有其他數據結構無法取代的地位。樹狀數組雖然也能解決很多問題，而且代碼量較低，空間復雜度較低，但是局限性較大，比如區間最值的問題就不能用樹狀數組完美解決。

? ? ? ? 那么接下來就為大家帶來線段樹的兩種基本用法：單點更新和區間更新（又叫成段更新）。

? ? ? ? 首先線段樹它是一棵高度平衡的二叉樹，那么很多二叉樹的性質它是完美繼承的，比如用數組去模擬的話，父節點的下標*2=左兒子的下標，父節點的下標*2+1=右兒子的下標。而這個性質也在線段樹的實現中得到了很好的運用（當然線段樹還有很多不同的寫法，大家可以自行研究，這里不做展開）。

? ? ? ? 那么什么是線段樹呢？

? ? ? ? 我們來看一道題：

HDU1166敵兵布陣

? ? ? ? 這道題如果用常規暴力的做法，就把所有營地的士兵存在一個數組里面，然后對于每次操作直接更新對應位置的數，對于每次詢問直接從i到j加起來。然而這么操作下來，對于極限數據50000個人，40000條命令，顯然是會超時的，那么一種新的數據結構線段樹就應運而生了。

? ? ? ? 首先第一個疑問：為什么線段樹會快？

? ? ? ? 顯然對于m個點n次詢問，暴力的做法時間復雜度是O（m*n）的。然而線段樹作為一棵二叉樹，繼承了二叉樹O（logn）的優良品質，對于這道題最壞的復雜度也是O（m*logn）的，這個量顯然是符合時間要求的。

? ? ? ? 第二：線段樹如何處理？

? ? ? ? 倘若節點x(x為奇數)記錄的是第1個點的數據，節點x+1記錄的是第2個點的數據，那么節點x/2記錄的就是區間[1,2]上的有效數據，以此類推，最頂端的父節點記錄的就是區間[1,n]上的有效數據，那么對于每個點的數據，有且僅有logn個節點的數據會被它影響，因此每次更新只用更新logn個點，查詢亦然，這樣就有效地節約了時間。

? ? ? ? 對于每個節點，其代表的是區間[x,y]之間的值，那么其左兒子節點代表的就是[x,(x+y)/2]區間的值，右兒子節點代表的是區間[(x+y)/2+1,y]上的值，既保證了無重復，又保證了樹的層數最短，查詢效率最高。

? ? ? ? 第三：線段樹的具體實現呢？

? ? ? ? 那么我們就跟著剛才拿到題目來詳細講解。

int tre[N*4]; void build(int num,int le,int ri) { if(le==ri) { scanf("%d",&tre[num]); return ; } int mid=(le+ri)/2; build(num*2,le,mid); build(num*2+1,mid+1,ri); tre[num]=tre[num*2]+tre[num*2+1]; }

?首先是建樹，在這里num存的是下標，而le和ri表示的是這個區間的左右端點，那么每往下一層num*2，區間則折半，保證了最少的層數，而此時內存占用大約為4倍的點數，所以開數組的時候開tre[4*N]。這個題因為需要讀入每個點，作為二叉樹的先序遍歷，很好地保證了第x個點正好讀入在le=ri=x的那個tre[num]里面。而父親節點所代表的區間包含了子節點所代表的區間，所以子節點的值又會影響父節點，因此每次建立完兒子節點之后，又會通過tre[num]=tre[num*2]+tre[num*2+1];操作將父親節點初始化，當然此處為求和操作所以是+，不同的題可以選擇取最值等不同運算符。當然不同的題根據需求可以采取對tre[num]賦值或者memset等方法來建樹以及初始化。

void update(int num,int le,int ri,int x,int y) { if(le==ri) { tre[num]+=y; return ; } int mid=(le+ri)/2; if(x<=mid) update(num*2,le,mid,x,y); else update(num*2+1,mid+1,ri,x,y); tre[num]=tre[num*2]+tre[num*2+1]; }

接下來是修改操作，繼承了上面的num，le，ri，保證了一致性，同時此處做的是對于第x個點增加y個人的操作，所以尋找到x所對應的tre[num]，然后操作，并回退。而此時需要注意的是，對于x操作了之后，所有包含x的區間的tre[num]都需要被修改，因此也就有了在回退前的tre[num]=tre[num*2]+tre[num*2+1];操作。而這個題操作的是增加減少（減少直接傳-x），而其他的諸如取最大最小值、取異或值等等都只用對于對應的運算符做修改即可。

int query(int num,int le,int ri,int x,int y) { if(x<=le&&y>=ri) { return tre[num]; } int mid=(le+ri)/2; int ans=0; if(x<=mid) ans+=query(num*2,le,mid,x,y); if(y>mid) ans+=query(num*2+1,mid+1,ri,x,y); return ans; }

最后是查詢操作，依然繼承了num，le，ri。而此處做的是區間查詢，（其實如果x=y就成了單點查詢）那么如果查詢區間[x,y]包含了目前的區間[le,ri]，即x<=le&&y>=ri，那么此時的tre[num]就已經是這一部分的有效數據了，所以直接return即可，否則繼續分區間查詢。同樣，此時根據題意所做的求和操作可以對應替換為異或、取最值等操作。

?

? ? ? ? 以上就是線段樹最簡單的功能——單點更新。

? ? ? ? 下面為大家帶來的線段樹稍微難一點但是基本是最常用的一個用法：區間更新。

區間更新對于初學者來說是一個坎，其中有幾步相對較難理解。但是只要掌握，就能解決絕大多數線段樹的題目了。

? ? ? ? 首先剛剛那個題每次是每個營地增減人，那么如果每次是x號營地到y號營地每次都增減人呢？這樣我們就會發現單點更新操作不適用了，無論我們如何調整都無法達到效果，而且即使每次對于x到y之間每個營地都執行一次單點操作，結果上看似可以，但是極限情況下我們每次對于1到n號進行更新的話，復雜度就會達到O(m*n*logn)，這樣就絕對會超時了，那么怎么做呢？這里就要用到區間更新了。

? ? ? ? 對于區間更新的，我們來看下面這個題：

HDU1556Color the ball

? ? ? ? 這個題很顯然滿足剛剛所提到的每次對于其中的一段里面的所有點進行操作。

? ? ? ? 那么既然是線段樹，首先我們依然是建樹初始化，在建樹階段區別不多，該讀值的讀值，該賦值的賦值，該置0的置0，這題根據需要，在最開始所有的球都是未被涂色的，那么直接所有tre[num]置為0即可，于是這一次我們就可以不必單獨寫一個build了，直接memset(tre,0,sizeof(tre))；即可。

? ? ? ? 但是與單點更新最大的不同就是：它多了一個lazy數組！！！！！！！！！！重要的地方要打10個感嘆號。

? ? ? ? laz，全稱lazy，中文叫懶惰標記或者延遲更新標記。

? ? ? ? 因為我們知道，如果我們每次都把段更新到節點上，那么操作次數和每次對區間里面的每個點單點更新是完全一樣的哇！那么怎么辦呢？仔細觀察線段樹，你會發現一個非常神奇的地方：每個節點表示的值都是區間[le,ri]之間的值有木有！！！！！！！！！！為什么說它神奇呢？更新的區間的值，存的區間的值！簡直就是天作之合，我每次更新到對應區間了我就放著，我等下次需要往下更新更小的區間的時候，再把兩次的值一起更新下去有木有啊！可以節約非常多時間啊有木有啊！

? ? ? ?對，這就是laz[num]的作用。下面我們跟著題再來逐步感受。

? ? ? ?首先在最最最最最最開始，是沒有進行過更新操作的，那么laz[num]自然是全部置為0（當然有的題有額外的初始化要求，大家根據題目自行定奪）。

? ? ? ?那么初始化結束之后，就開始更新操作。

void update(int num,int le,int ri,int x,int y) { if(x<=le&&y>=ri) { tre[num]++; laz[num]++; return ; } pushdown(num); int mid=(le+ri)/2; if(x<=mid) update(num*2,le,mid,x,y); if(y>mid) update(num*2+1,mid+1,ri,x,y); }

這一段是對區間[x,y]上的每個氣球都涂色一次，當然你也可以涂z次色，無非就是額外再傳一個變量代表涂色次數嘛。然后依然是分區間查找，一直到目標區間[x,y]包含了當前區間[le,ri]，那么就對tre[num]和laz[num]操作，代表對這個區間我這么修改，而這個區間的分區間也應該被做修改，但是這時候我為了節約時間，暫時不做修改，但是我把這個修改動作存在laz[num]里，下次需要的時候再修改。

?

? ? ? ?而下次是什么時候呢？就是當前區間比我需要的目標區間大的時候，我必須用到下面的值了，那么就迫不得已了，不能再懶惰下去了，必須往下修改了，這時候，我們就把之前堆積起來的懶惰標記pushdown了，于是就有了一個神奇的pushdown操作。

void pushdown(int num) { if(laz[num]!=0) { tre[num*2]+=laz[num]; tre[num*2+1]+=laz[num]; laz[num*2]+=laz[num]; laz[num*2+1]+=laz[num]; laz[num]=0; } }

?以上就是這個題的pushdown操作。當laz[num]!=0時，也就是這個點存在懶惰標記的時候，我們就要往下更新了，然而這個題是否判斷laz[num]的有無對整體影響不大，但是有部分題再pushdown的同時會對整體有影響，例如取最小值的時候對于一段同時置為一個數，那么如果不判斷0,就會把0給誤pushdown下去，這就必須判斷laz[num]的有無了。

?

? ? ? ? 那么laz[num]本來是應該修改下去的，所以會對兩個兒子節點的tre[num]有影響，這里因為是求加，所以采用的是+號，其它操作根據具體題目替換。同時，兒子節點的兒子節點也應該被更新，但是我們依然懶，趕一步走一步，所以此時依然不更新兒子節點的兒子節點，而是用更新兒子節點的laz標記來代替。

? ? ? ? 回到之前的updata操作，在每次修改了兒子節點的tre[num]之后，正常情況下應該對父親節點的tre[num]進行修改，但是此題父親節點的tre[num]不會對后面的結果造成影響，所以這里就偷懶省略了這一步操作，實際操作中絕大部分題目都是不可以省略的，必須在更新完兒子節點的值之后再反過來更新父親節點。

? ? ? ? 最后依然是query操作。

int query(int num,int le,int ri,int x) { if(le==ri) { return tre[num]; } pushdown(num); int mid=(le+ri)/2; if(x<=mid) return query(num*2,le,mid,x); else return query(num*2+1,mid+1,ri,x); }

與單點更新時的query非常相似（廢話吼，線段樹本來就是一個比較模板的東西），也是額外加了一個pushdown操作，原因與update的一樣，最后也缺省了反過來對父親節點的更新，原因同上，不再贅述。

?

?

? ? ? ? 至此線段樹的兩種基本用法：單點更新和區間更新操作就已經介紹完畢了。相信大家如果能仔細看完的話，對于這個數據結構也應該有了一定的認識。而線段樹還有掃描線、區間合并等高級用法，而且線段樹作為一個數據結構，是必然會和其它算法發生化學反應的，例如矩陣、dp等操作都有可能被巧妙地嵌套在線段樹上形成一個綜合題，所以大家下去一定要多做題，多感悟，才能深入透徹地吃下這個知識點。

?

?

<---------------------------------------------------------------------------------------------------------------------------------------------------------->

void update(int i,int k,int val,int q){//單個點的更新if( A[i].lt == k && A[i].rt == k ){if( q ){A[i].val += val;}else{A[i].val -= val;}return ;}if( k <= A[i<<1].rt ){update( i<<1,k,val,q );//自己體會}if( k>= A[i<<1|1].lt ){update( i<<1|1,k,val,q );}A[i].val = (A[i<<1].val + A[i<<1|1].val ); }int query(int i,int lt,int rt){if( A[i].lt >= lt && A[i].rt <= rt ){return A[i].val;}int a = 0;int b = 0;if( lt <= A[i<<1].rt ){//左區間有涉及就向左查詢a = query( i<<1,lt,rt );}if( rt >= A[i<<1|1].lt ){//右區間有涉及就向右查詢b = query( i<<1|1,lt,rt );}return (a+b); }

?

轉載于:https://www.cnblogs.com/yakoazz/p/5877187.html

總結

以上是生活随笔為你收集整理的（转）线段树的区间更新的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。