之前說了線段樹的點更新和區間求和。其實點更新是區間更新的一種最基礎的做法。我們把一個點想像成一個區間的話，不就是最簡單的區間更新了嘛。
為什么要把區間更新和點更新分開來看呢？假如我們對區間[l,r]進行更新，我們對這一段區間進行r-l+1次點更新不就行了嘛？這樣結果確實沒有錯誤，但是這樣的話，時間復雜度會非常高，區間更新的題目如果這么做肯定會超時的。那么我們就引進了區間更新了。
這里引入了一個標記數組，lazy[maxn<<2]。lazy數組是區間更新中的精髓所在，lazy的意思就是懶的意思。我們對于每一次區間更新，我們并不直接一次更新到底，而是用lazy標記著更新了多少，等到需要的時候，我們再更新。
簡單的說就是，我們把向下的修改先儲存起來，而對于每個查詢我們在向上傳遞答案的時候加上這些修改的值。
那區間更新+區間求和來說：
對于任意一段[l,r]區間加上一個數v,然后對任意區間求和。

inline void pushup(int cur)//pushup和之前的含義是一樣的 {p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum; } inline void pushdown(int cur)//重點重點重點 {if(p[cur].lazy)//如果存在延遲更新的話{p[cur<<1].lazy+=p[cur].lazy;p[cur<<1|1].lazy+=p[cur].lazy;//左右兒子節點的lazy加上父親節點的lazyp[cur<<1].sum+=(p[cur<<1].r-p[cur<<1].l+1)*p[cur].lazy;p[cur<<1|1].sum+=(p[cur<<1|1].r-p[cur<<1|1].l+1)*p[cur].lazy;//每個節點都加上了lazy，這樣的話，一共就加上了區間長度個lazy。p[cur].lazy=0;//執行完上面的操作后就將lazy清零。} }

區間更新模板

const int maxx=1e5+100; struct node{int l;int r;int sum;int lazy; }p[maxx<<2]; inline void pushup(int cur) {p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum; } inline void pushdown(int cur) {if(p[cur].lazy){p[cur<<1].lazy+=p[cur].lazy;p[cur<<1|1].lazy+=p[cur].lazy;p[cur<<1].sum+=(p[cur<<1].r-p[cur<<1].l+1)*p[cur].lazy;p[cur<<1|1].sum+=(p[cur<<1|1].r-p[cur<<1|1].l+1)*p[cur].lazy;p[cur].lazy=0;} } inline void build(int l,int r,int cur)//一如既往的建樹操作 {p[cur].l=l;p[cur].r=r;p[cur].sum=p[cur].lazy=0;if(l==r){p[cur].sum=a[l];return ;}int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);pushup(cur); } inline void update(int l,int r,int cur,int v) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r)//如果當前區間在要更新的區間中，就可以停止遞歸，轉為lazy標記{p[cur].sum+=(R-L+1)*v;p[cur].lazy+=v;return ;}pushdown(cur);//現在要更新下面的子節點了，因此我們要先將之前的lazy標記下放，否則會出錯。int mid=L+R>>1;if(r<=mid) update(l,r,cur<<1,v);else if(l>mid) update(l,r,cur<<1|1,v);else {update(l,mid,cur<<1,v);update(mid+1,r,cur<<1|1,v);}pushup(cur); } inline int query(int l,int r,int cur)//求和操作，和update的含義是一樣的。 {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].sum;pushdown(cur);int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else return query(l,mid,cur<<1)+query(mid+1,r,cur<<1|1); }

線段樹的魅力并不在于這里，而是線段樹和其他的算法巧妙的結合在一起，例如DP以及矩陣等，會產生很多有意思的算法。除此之外，線段樹的區間合并以及掃描線等也是很有意思的。
努力加油a啊，(^o)/~

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的数据结构之线段树进阶（区间更新lazy标记）的全部內容，希望文章能夠幫你解決所遇到的問題。

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