線段樹進階-區間修改

09-11

線段樹進階-區間修改

來自專欄程序員的成長之路

上篇文章我們說了線段樹的建樹更新訪問修改節點

那麼如果我們想改變一個區間里的所有值怎麼辦：比如我想讓編號為2-5的節點的值都加2，線段樹維護的是區間和。我們難道要訪問到所有的子節點然後修改？ O(n)的複雜度顯然是我們接受不了的，那麼我們如何解決呢？

答案就是打上標記，類似於訪問操作，我們在根節點不斷向下訪問，直到訪問區間完全被要求區間所包含，然後打上標記，不改變本節點的值，然後遞歸改變祖先節點的值。這點很重要，因為該節點的值只要不被訪問就不用去掉標記和將標記下移，但是祖先節點的值必須要改變，切記切記。

當我們訪問的時候就要注意了，要看被訪問的節點是否帶標記，如果有標記的話，改變數值，標記下移。

這就是修改區間的思路，下面給一個例題和題解，大家可以去解決一下

【P3372】【模板】線段樹 1 - 洛谷?

www.luogu.org

#include<bits/stdc++.h>using namespace std;#define getl(x) (x<<1)#define getr(x) (x<<1|1)struct node{ long long left; long long right; long long v; long long add; node(long long x=0,long long y=0,long long z=0) { left = x; right = y; v = z; add=0; }};long long n,m;const long long maxn = 100001;long long date[maxn<<2];node tree[maxn<<2];void pushup(long long post){ tree[post].v = tree[getl(post)].v+tree[getr(post)].v+(tree[getl(post)].right-tree[getl(post)].left+1)*tree[getl(post)].add+(tree[getr(post)].right-tree[getr(post)].left+1)*tree[getr(post)].add;}void build(long long root,long long start,long long end){ tree[root].left = start; tree[root].right = end; if(start==end) { tree[root].v = date[start]; return; } long long mid = (start+end)/2; build(getl(root),start,mid); build(getr(root),mid+1,end); pushup(root);}void point_change(long long x,long long v,long long root){ if(tree[root].right==tree[root].left) { tree[root].v += v; return; } long long mid = (tree[root].right+tree[root].left)>>1; if(mid<x) point_change(x,v,getr(root)); else point_change(x,v,getl(root)); pushup(root);}void line_change(long long cs,long long ce,long long v,long long root){ if(cs<=tree[root].left&&tree[root].right<=ce) { tree[root].add += v; return; } long long mid = (tree[root].right+tree[root].left)>>1; if(cs<=mid) line_change(cs,ce,v,getl(root)); if(ce>mid) line_change(cs,ce,v,getr(root)); pushup(root);}long long ask(long long start,long long end,long long root){ if(tree[root].add!=0) { tree[root].v+=(tree[root].right-tree[root].left+1)*tree[root].add; if(tree[root].left!=tree[root].right) { tree[getl(root)].add+= tree[root].add; tree[getr(root)].add+= tree[root].add; } tree[root].add = 0; } if(start<=tree[root].left&&tree[root].right<=end) { return tree[root].v; } long long mid = (tree[root].right+tree[root].left)>>1; long long ans = 0; if(start<=mid) ans+=ask(start,end,getl(root)); if(end>mid) ans+=ask(start,end,getr(root)); return ans;}void init(){ cin>>n>>m; for(long long i=1; i<=n; i++) { cin>>date[i]; } build(1,1,n);}void AC(){ init(); long long x,y,z,w; for(long long i=0;i<m;i++) { cin>>x; if(x==1) { cin>>y>>z>>w; line_change(y,z,w,1); } else { cin>>y>>z; cout<<ask(y,z,1)<<endl; } }}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); AC(); return 0;}

希望大家可以去動手實踐一下，實踐出真知嘛，那我們下篇文章再見了。