本文主要是介绍poj3468(线段树成段更新模板题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和
下面的介绍是下解题思路：
首先介绍 lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。
比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，它的节点标记为o，这时tree[o].l == a && tree[o].r == b 这时我们可以一步更新此时o节点的sum[o]的值，sumo] += c * (tree[o].r - tree[o].l + 1)，注意关键的时刻来了，如果此时按照常规的线段树的update操作，这时候还应该更新o子节点的sum[]值，而Lazy思想恰恰是暂时不更新o子节点的sum[]值，到此就return，直到下次需要用到o子节点的值的时候才去更新，这样避免许多可能无用的操作，从而节省时间 。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define ll __int64
#define N 100005
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
struct Node
{int l,r;ll sum,add;
}tree[N<<2];
ll a[N];
void PushUp(int o)//用于更新根节点
{tree[o].sum = tree[2*o].sum + tree[2*o+1].sum;
}
void build(int o,int l,int r)
{tree[o].l = l;tree[o].r = r;tree[o].add = 0;if(l == r){tree[o].sum = a[l];return;}int m = (l+r)/2;build(2*o,l,m);build(2*o+1,m+1,r);PushUp(o);
}
void PushDown(int o)//用于更新子节点
{int m = (tree[o].r-tree[o].l+1);if( tree[o].add){tree[2*o].add += tree[o].add;tree[2*o+1].add += tree[o].add;tree[2*o].sum += tree[o].add*(m - (m>>1));tree[2*o+1].sum += tree[o].add*(m>>1);tree[o].add = 0;}
}
void update(int o,int x,int y,int v)
{if(x == tree[o].l && tree[o].r == y){tree[o].add += v;//这个标记用来延迟更新tree[o].sum += (__int64)v*(y-x+1);return ;}if(tree[o].l == tree[o].r) return;PushDown(o);int m = (tree[o].r+tree[o].l)/2;if(y <= m)update(2*o,x,y,v);else if(x > m)update(2*o+1,x,y,v);else {update(2*o, x, m, v);update(2*o+1, m+1, y, v);}PushUp(o);
}
ll query(int o,int x,int y)
{if(tree[o].l == x && tree[o].r == y)return tree[o].sum;PushDown(o);ll res = 0;int m = (tree[o].l+tree[o].r)/2;if(y <= m) res += query(2*o,x,y);else if(x > m) res += query(2*o+1,x,y);else {res += query(2*o,x,m);res += query(2*o+1,m+1,y);}return res;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n,m;while(scanf("%d%d",&n,&m) != EOF){int i;for(i = 1; i <= n; i++)scanf("%I64d",&a[i]);build(1,1,n);char str[5];while(m--){scanf("%s",str);int x,y,z;if(str[0] == 'C'){scanf("%d%d%d",&x,&y,&z);update(1,x,y,z);}if(str[0] == 'Q'){scanf("%d%d",&x,&y);printf("%I64d\n",query(1,x,y));}}}return 0;
}最后还有几点补充，
在update函数中，if(tree[o].l == x && y == tree[o].r) 这里就是用到Lazy思想的关键时刻 正如上面说提到的，这里首先更新该节点的sum[o]值，然后更新该节点具体每个数值应该加多少即add[o]的值，注意此时整个函数就运行完了，直接return，而不是还继续向子节点继续更新，这里就是Lazy思想，暂时不更新子节点的值。那么什么时候需要更新子节点的值呢？答案是在某部分update操作的时候需要用到那部分没有更新的节点的值的时候，这时就掉用PushDown()函数更新子节点的数值。
对于PushDown()函数，就是从当前根节点rt向下更新每个子节点的值，这段代码读者可以自己好好理解，这也是Lazy的关键。
这篇关于poj3468(线段树成段更新模板题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
