POJ 3468 A Simple Problem with Integers(段更新的区间求和Lazy思想线段树)

本文主要是介绍POJ 3468 A Simple Problem with Integers(段更新的区间求和Lazy思想线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：[kuangbin带你飞]专题七线段树 C - A Simple Problem with Integers

题意

给定n个数及m个操作。
操作分两种：
1. C a b c，表示对区间ab整体全部加上c
2. Q a b ，对区间ab求和并输出。

思路

看到段更新，第一反应是给点更新外面加个for，但显然不可行。
了解到有个Lazy思想，即记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。
这个思想可以简单的用一个比喻来描述：一个四口之家每月都可以领国家的补贴，国家发放时自然是发到他们整体，那么孩子与父母分家后呢，怎么办，这时就需要在牠们家庭的基础上进一步分开分配了(例子不是很形象，大概就是这个意思)。
我们用两个数组Sum和Add，Sum表示当前区间的和，Add表示当前区间所整体增加的值。
两个操作，PushUp(子向父更新)，PushDown(父向子更新)
继续上面的比喻，你是那个四口之家的小孩，平日里补贴肯定是到不了你手上，所以也就没必要去算你到底有多少，那么当你某时需要用呢(进行求和操作时)，你再问父亲要(这个时候进行PushDown操作)。
这样的话，在update就免去了很多不必要的操作，效率大大提升。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>using namespace std;const int N = 100009;
const int MAX = N*3;
long long Sum[MAX], Add[MAX] = {};void PushUp(int k)
{Sum[k] = Sum[k<<1] + Sum[k<<1 | 1];
}void PushDown(int k, int num)
{if(!Add[k])return;Add[k<<1] += Add[k];Add[k<<1 | 1] += Add[k];Sum[k<<1] += ((num+1)>>1)*Add[k];Sum[k<<1 | 1] += (num>>1)*Add[k];Add[k] = 0;
}void build(int l, int r, int k)
{Add[k] = 0;if(l == r){scanf("%lld", &Sum[k]);return;}int mid = (l+r)>>1;build(l, mid, k<<1);build(mid+1, r, k<<1 | 1);PushUp(k);
}void update(int l, int r, int tol, int tor, int d, int k)
{if(tol <= l && tor >= r){Add[k] += d;Sum[k] += d*(r-l+1);return;}PushDown(k, r-l+1);int mid = (l+r)>>1;if(tol <= mid)update(l, mid, tol, tor, d, k<<1);if(tor > mid)update(mid+1, r, tol, tor, d, k<<1 | 1);PushUp(k);
}long long find(int l, int r, int tol, int tor, int k)
{if(tol <= l && tor >= r)return Sum[k];PushDown(k, r-l+1);int mid = (l+r)>>1;long long ans = 0;if(tol <= mid)ans += find(l, mid, tol, tor, k<<1);if(tor > mid)ans += find(mid+1, r, tol, tor, k<<1 | 1);return ans;
}int main()
{int n, m;scanf("%d%d", &n, &m);build(1, n, 1);char str[10];int i, j, k;while(m--){scanf("%s", str);if(str[0] == 'C'){scanf("%d%d%d", &i, &j, &k);update(1, n, i, j, k, 1);}else{scanf("%d%d", &i, &j);printf("%lld\n" ,find(1, n, i, j, 1));}}return 0;
}