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;
}