POJ 3468 A Simple Problem with Integers

时间：2010-05-13 来源：MC_ACM

题目大意：给出N个数，有两种操作，一种是查询，给出一个区间，求出数组区间的和，另一种是给出一个区间和一整数，区间内的数都加上这个整数。
解题思路

利用线段树结构。用普通的的没有优化的线段树做的话会超时。有一个优化：每次插入一个数字时，没必要把数字一直插入到叶子节点，只要有当前节点的范围和插入的范围是一样的，那么就没有必要往下继续插入。用一个增量表示这个范围内的每个元素的增量。在求和的时候再从这个增量乘以范围加到和当中。如果当前范围包括了查询范围，就查询它的子节点，把增量传递给它的子节点。

对于Q操作，求出区间的总和，对于C操作，将区间里的所有数都加上同一个数考虑结点存放两个信息，一个是该结点区间内的和s，一个是该区间所有数的增量d,对于一个C操作，如果区间刚好等于某结点的区间，则直接将增量加上去，否则，递归到左右子结点，并更新父结点的s值。这样，对于插入与查询都能达到O(logn)的复杂度.

#include <iostream>
using namespace std;
#define ll long long
const int MAXN = 100001;
struct {
    int l, r;
    ll s, d; // s为和、d为增量

} nod[MAXN*3]; //定义节点

int a[MAXN];
void creat(int t, int l, int r) { //建立线段树

    if(l == r) {
        nod[t].l = nod[t].r = l, nod[t].s = a[l], nod[t].d = 0;
        return;
    }
    int m = (l+r) / 2;
    nod[t].l = l, nod[t].r = r, nod[t].d = 0;
    creat(t*2, l, m), creat(t*2+1, m+1, r);
    nod[t].s = nod[t*2].s + nod[t*2+1].s;
}
void inc(int t, int l, int r, int c) { //增加修改函数

    if(l == nod[t].l && r == nod[t].r) {nod[t].d += c; return;}
    if(r <= nod[t*2].r) inc(t*2, l, r, c);
    else if(l >= nod[t*2+1].l) inc(t*2+1, l, r, c);
    else inc(t*2, l, nod[t*2].r, c), inc(t*2+1, nod[t*2+1].l, r, c);
    nod[t].s = nod[t*2].s + nod[t*2].d * (nod[t*2].r-nod[t*2].l+1) + nod[t*2+1].s + nod[t*2+1].d * (nod[t*2+1].r-nod[t*2+1].l+1);
}
ll query(int t, int l, int r) { //查询操作函数

    if(nod[t].l == l && nod[t].r == r) return nod[t].s + nod[t].d * (r-l+1);
    ll sum;
    if(r <= nod[t*2].r) sum = query(t*2, l, r);
    else if(l >= nod[t*2+1].l) sum = query(t*2+1, l, r);
    else sum = query(t*2, l, nod[t*2].r) + query(t*2+1, nod[t*2+1].l, r);
    return sum + nod[t].d * (r-l+1);
}
int main() {
    int i, n, q, x1, x2, c;
    char s[2];
    while(scanf("%d%d", &n, &q) != EOF) {
        for(i = 1; i <= n; i++) scanf("%d", &a[i]);
        creat(1, 1, n);
        while(q--) {
            scanf("%s%d%d", s, &x1, &x2);
            if(s[0] == 'C') {scanf("%d", &c); inc(1, x1, x2, c);}
            else printf("%lld\n", query(1, x1, x2));
        }
    }
    return 0;
}