http://poj.org/problem?id=3468
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
解题思路：仍是典型的线段树应用，只不过增加了更新值部分的代码。需要注意的是，操作时要"按需"更新，不要每次都更新到叶子节点，不然就失去了使用线段树的意义。The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
对于本题，可以在树节点中设置一个 delta 变量，仅当需要向下更新时，才将 delta 变量的值传下去，否则只改动当前节点的 delta 即可，从而起到"缓冲"的作用。
const int MAXN = 100001;int numbers[MAXN];struct st { // 区间范围 int left, right; // 更新值、区间总和 long long delta, sum;} st[MAXN * 4];// 建树代码基本不变void build(int root, int l, int r) { st[root].left = l, st[root].right = r, st[root].delta = 0; if (l == r) { st[root].sum = numbers[l]; return; } int m = l + ((r - l) >> 1); build(L(root), l, m); build(R(root), m + 1, r); st[root].sum = st[L(root)].sum + st[R(root)].sum;}long long query(int root, int l, int r) { // 如查询区间恰等于节点区间，直接返回该区间总和即可 if (st[root].left == l && st[root].right == r) { return st[root].sum; } // 否则需将当前区间的“缓冲”值更新下去并修正各节点区间的总和 if (st[root].delta) { st[L(root)].delta += st[root].delta; st[R(root)].delta += st[root].delta; st[L(root)].sum += st[root].delta * (st[L(root)].right - st[L(root)].left + 1); st[R(root)].sum += st[root].delta * (st[R(root)].right - st[R(root)].left + 1); st[root].delta = 0; } int m = st[root].left + ((st[root].right - st[root].left) >> 1); if (r <= m) { return query(L(root), l, r); } else if (l > m) { return query(R(root), l, r); } else { return query(L(root), l, m) + query(R(root), m + 1, r); }}void update(int root, int l, int r, long long v) { // 如变更区间恰等于节点区间，只修正当前节点区间即可 if (st[root].left == l && st[root].right == r) { st[root].delta += v; st[root].sum += v * (r - l + 1); return; } // 否则需向下修正相关节点区间 if (st[root].delta) { st[L(root)].delta += st[root].delta; st[R(root)].delta += st[root].delta; st[L(root)].sum += st[root].delta * (st[L(root)].right - st[L(root)].left + 1); st[R(root)].sum += st[root].delta * (st[R(root)].right - st[R(root)].left + 1); st[root].delta = 0; } int m = st[root].left + ((st[root].right - st[root].left) >> 1); if (r <= m) { update(L(root), l, r, v); } else if (l > m) { update(R(root), l, r, v); } else { update(L(root), l, m, v); update(R(root), m + 1, r, v); } // 同时一定要记得修正当前节点区间的总和 st[root].sum = st[L(root)].sum + st[R(root)].sum;}int main() { int N, Q; while (scanf("%d%d", &N, &Q) != EOF) { for (int i = 1; i <= N; ++i) { scanf("%d", &numbers[i]); } build(1, 1, N); char cmd; int l, r; long long v; while (Q--) { scanf(" %c", &cmd); scanf("%d%d", &l, &r); switch (cmd) { case 'Q': printf("%lld\n", query(1, l, r)); break; case 'C': scanf("%lld", &v); if (v) { update(1, l, r, v); } break; } } } return 0;}