首页 > 代码库 > 线段树区间更新操作及Lazy思想(详解)
线段树区间更新操作及Lazy思想(详解)
此题题意很好懂：
给你N个数，Q个操作，操作有两种，‘Q a b ’是询问a~b这段数的和，‘C a b c’是把a~b这段数都加上c。
需要用到线段树的，update:成段增减，query:区间求和
介绍Lazy思想：lazy－tag思想，记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。
在此通俗的解释我理解的Lazy意思，比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，它的节点标记为rt，这时tree[rt].l== a && tree[rt].r == b 这时我们可以一步更新此时rt节点的sum[rt]的值，sum[rt] += c* (tree[rt].r - tree[rt].l + 1)，注意关键的时刻来了，如果此时按照常规的线段树的update操作，这时候还应该更新rt子节点的sum[]值，而Lazy思想恰恰是暂时不更新rt子节点的sum[]值，到此就return，直到下次需要用到rt子节点的值的时候才去更新，这样避免许多可能无用的操作，从而节省时间。
下面通过具体的代码来说明之。
在此先介绍下代码中的函数说明：
#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1
宏定义左儿子lson和右儿子rson，貌似用宏的速度要慢。
PushUp(rt)：通过当前节点rt把值递归向上更新到根节点
PushDown(rt)：通过当前节点rt递归向下去更新rt子节点的值
rt表示当前子树的根(root),也就是当前所在的结点
1 __int64 sum[N<<2],add[N<<2];2 struct Node3 {4 int l,r;5 int mid()6 {7 return (l+r)>>1;8 }9 } tree[N<<2];
这里定义数据结构sum用来存储每个节点的子节点数值的总和，add用来记录该节点的每个数值应该加多少
tree[].l tree[].r分别表示某个节点的左右区间，这里的区间是闭区间
下面直接来介绍update函数，Lazy操作主要就是用在这里
1 void update(int c,int l,int r,int rt)//表示对区间[l,r]内的每个数均加c，rt是根节点 2 { 3 if(tree[rt].l == l && r == tree[rt].r) 4 { 5 add[rt] += c; 6 sum[rt] += (__int64)c * (r-l+1); 7 return; 8 } 9 if(tree[rt].l == tree[rt].r) return;10 PushDown(rt,tree[rt].r - tree[rt].l + 1);11 int m = tree[rt].mid();12 if(r <= m) update(c,l,r,rt<<1);13 else if(l > m) update(c,l,r,rt<<1|1);14 else15 {16 update(c,l,m,rt<<1);17 update(c,m+1,r,rt<<1|1);18 }19 PushUp(rt);20 }
if(tree[rt].l == l && r == tree[rt].r) 这里就是用到Lazy思想的关键时刻
正如上面说提到的，这里首先更新该节点的sum[rt]值，然后更新该节点具体每个数值应该加多少即add[rt]的值，注意此时整个函数就运行完了，直接return，而不是还继续向子节点继续更新，这里就是Lazy思想，暂时不更新子节点的值。
那么什么时候需要更新子节点的值呢？答案是在某部分update操作的时候需要用到那部分没有更新的节点的值的时候，这里可能有点绕口。这时就掉用PushDown()函数更新子节点的数值。
1 void PushDown(int rt,int m) 2 { 3 if(add[rt]) 4 { 5 add[rt<<1] += add[rt]; 6 add[rt<<1|1] += add[rt]; 7 sum[rt<<1] += add[rt] * (m - (m>>1)); 8 sum[rt<<1|1] += add[rt] * (m>>1); 9 add[rt] = 0;//更新后需要还原10 }11 }
PushDown就是从当前根节点rt向下更新每个子节点的值，这段代码读者可以自己好好理解，这也是Lazy的关键。
下面再解释query函数，也就是用这个函数来求区间和
1 __int64 query(int l,int r,int rt) 2 { 3 if(l == tree[rt].l && r == tree[rt].r) 4 { 5 return sum[rt]; 6 } 7 PushDown(rt,tree[rt].r - tree[rt].l + 1); 8 int m = tree[rt].mid(); 9 __int64 res = 0;10 if(r <= m) res += query(l,r,rt<<1);11 else if(l > m) res += query(l,r,rt<<1|1);12 else13 {14 res += query(l,m,rt<<1);15 res += query(m+1,r,rt<<1|1);16 }17 return res;18 }
第一个if还是区间的判断和前面update的一样，到这里就可以知道答案了，所以就直接return。
接下来的查询就需要用到rt子节点的值了，由于我们用了Lazy操作，这段的数值还没有更新，因此我们需要调用PushDown函数去更新之，满足if(add[rt])就说明还没有更新。
到这里整个Lazy思想就算介绍结束了，可能我的语言组织不是很好，如果有不理解的地方可以给我留言，我再解释大家的疑惑。
PS：今天总算是对线段树入门了。
附上此题的代码：
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int N = 100005; 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 8 __int64 sum[N<<2],add[N<<2]; 9 struct Node 10 { 11 int l,r; 12 int mid() 13 { 14 return (l+r)>>1; 15 } 16 } tree[N<<2]; 17 18 void PushUp(int rt) 19 { 20 sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 21 } 22 23 void PushDown(int rt,int m) 24 { 25 if(add[rt]) 26 { 27 add[rt<<1] += add[rt]; 28 add[rt<<1|1] += add[rt]; 29 sum[rt<<1] += add[rt] * (m - (m>>1)); 30 sum[rt<<1|1] += add[rt] * (m>>1); 31 add[rt] = 0; 32 } 33 } 34 35 void build(int l,int r,int rt) 36 { 37 tree[rt].l = l; 38 tree[rt].r = r; 39 add[rt] = 0; 40 if(l == r) 41 { 42 scanf("%I64d",&sum[rt]); 43 return ; 44 } 45 int m = tree[rt].mid(); 46 build(lson); 47 build(rson); 48 PushUp(rt); 49 } 50 51 void update(int c,int l,int r,int rt) 52 { 53 if(tree[rt].l == l && r == tree[rt].r) 54 { 55 add[rt] += c; 56 sum[rt] += (__int64)c * (r-l+1); 57 return; 58 } 59 if(tree[rt].l == tree[rt].r) return; 60 PushDown(rt,tree[rt].r - tree[rt].l + 1); 61 int m = tree[rt].mid(); 62 if(r <= m) update(c,l,r,rt<<1); 63 else if(l > m) update(c,l,r,rt<<1|1); 64 else 65 { 66 update(c,l,m,rt<<1); 67 update(c,m+1,r,rt<<1|1); 68 } 69 PushUp(rt); 70 } 71 72 __int64 query(int l,int r,int rt) 73 { 74 if(l == tree[rt].l && r == tree[rt].r) 75 { 76 return sum[rt]; 77 } 78 PushDown(rt,tree[rt].r - tree[rt].l + 1); 79 int m = tree[rt].mid(); 80 __int64 res = 0; 81 if(r <= m) res += query(l,r,rt<<1); 82 else if(l > m) res += query(l,r,rt<<1|1); 83 else 84 { 85 res += query(l,m,rt<<1); 86 res += query(m+1,r,rt<<1|1); 87 } 88 return res; 89 } 90 91 int main() 92 { 93 int n,m; 94 while(~scanf("%d %d",&n,&m)) 95 { 96 build(1,n,1); 97 while(m--) 98 { 99 char ch[2];100 scanf("%s",ch);101 int a,b,c;102 if(ch[0] == ‘Q‘)103 {104 scanf("%d %d", &a,&b);105 printf("%I64d\n",query(a,b,1));106 }107 108 else109 {110 scanf("%d %d %d",&a,&b,&c);111 update(c,a,b,1);112 }113 }114 }115 return 0;116 }
线段树区间更新操作及Lazy思想(详解)