题意：给出一个数组A，数组来度为N，接着来Q个操作，操作有两种，C a b c：将数组A在[a, b]上的值全部加c，Q a b：询问数组A在[a, b]上的区间和。
题目链接：http://poj.org/problem?id=3468
——>>数据量之大，直接for统计与修改的结果该是TLE，这也正是线段树区间修改的模版题，照着白书加强版的思路与提示WA了十余次也没过，最后换了下传增量的写法，终于给了我一个AC!
原想，8个叶子的线段树，就2*8-1个结点，对于maxn个叶子，开2*maxn的空间够了，事实证明，不够，对于本题来说，开3*maxn的空间足够，不过发现比较多的写法开了4*maxn的空间，空间不够，我尝到了两种结果，一种是RE，另一种是WA。
把查询区间传到函数参数里，写出来的代码长长的（1594ms），于是改用全局变量来做，却发现，这样做运行时间变长了（1657ms）。
全局变量写法：
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 100000 + 10;
long long sumv[3*maxn], addv[3*maxn], a[maxn], _sum, y1, y2, v;
//sumv[o]表示如果只执行结点o及其子孙结点的add的区间和，_sum为要求的结果，a为输入数组，addv[o]表示结点o被加了多少，y1、y2为改动区间，v为改动量void build(int o, int L, int R) //建树,给sumv赋初值
{if(L == R) sumv[o] = a[L];else{int M = L + (R-L) / 2;if(L <= M) build(2*o, L, M);if(R > M) build(2*o+1, M+1, R);sumv[o] = sumv[2*o] + sumv[2*o+1];}
}
void update(int o, int L, int R) //更新
{if(y1 <= L && R <= y2){addv[o] += v; //记录增量return;}else if(L <= y1 && y2 <= R) sumv[o] += v * (y2-y1+1); //加上增量else if(y1 <= L && y2 <= R) sumv[o] += v * (y2-L+1); //加上增量else if(L <= y1 && R <= y2) sumv[o] += v * (R-y1+1); //加上增量int M = L + (R-L) / 2;if(y1 <= M) update(2*o, L, M);if(y2 > M) update(2*o+1, M+1, R);
}
void query(int o, int L, int R) //查询
{if(y1 <= L && R <= y2){_sum += sumv[o] + addv[o] * (R-L+1); //加上自己的增量return;}addv[2*o] += addv[o]; //增量下传addv[2*o+1] += addv[o]; //增量下传sumv[o] += addv[o] * (R-L+1); //更新sumv值addv[o] = 0; //修改增量int M = L + (R-L) / 2;if(y1 <= M) query(2*o, L, M);if(y2 > M) query(2*o+1, M+1, R);
}
int main()
{int N, Q, i;char s[7];scanf("%d%d", &N, &Q);for(i = 1; i <= N; i++) scanf("%I64d", &a[i]);build(1, 1, N); //建树memset(addv, 0, sizeof(addv));while(Q--){scanf("%s", s);if(s[0] == 'Q'){scanf("%I64d%I64d", &y1, &y2);_sum = 0;query(1, 1, N);printf("%I64d\n", _sum);}else{scanf("%I64d%I64d%I64d", &y1, &y2, &v);update(1, 1, N);}}return 0;
}
传参写法：
#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 100000 + 10;
long long sumv[3*maxn], addv[3*maxn], a[maxn], _sum;
//sumv[o]表示如果只执行结点o及其子孙结点的add的区间和，_sum为要求的结果，a为输入数组，addv[o]表示结点o被加了多少void build(int o, int L, int R) //建树,给sumv赋初值
{if(L == R) sumv[o] = a[L];else{int M = L + (R-L) / 2;if(L <= M) build(2*o, L, M);if(R > M) build(2*o+1, M+1, R);sumv[o] = sumv[2*o] + sumv[2*o+1];}
}
void update(int o, int L, int R, int y1, int y2, long long v) //更新
{if(y1 <= L && R <= y2){addv[o] += v; //记录增量return;}else if(L <= y1 && y2 <= R) sumv[o] += v * (y2-y1+1); //加上增量else if(y1 <= L && y2 <= R) sumv[o] += v * (y2-L+1); //加上增量else if(L <= y1 && R <= y2) sumv[o] += v * (R-y1+1); //加上增量int M = L + (R-L) / 2;if(y1 <= M) update(2*o, L, M, y1, y2, v);if(y2 > M) update(2*o+1, M+1, R, y1, y2, v);
}
void query(int o, int L, int R, int y1, int y2) //查询
{if(y1 <= L && R <= y2){_sum += sumv[o] + addv[o] * (R-L+1); //加上自己的增量return;}addv[2*o] += addv[o]; //增量下传addv[2*o+1] += addv[o]; //增量下传sumv[o] += addv[o] * (R-L+1); //更新sumv值addv[o] = 0; //修改增量int M = L + (R-L) / 2;if(y1 <= M) query(2*o, L, M, y1, y2);if(y2 > M) query(2*o+1, M+1, R, y1, y2);
}
int main()
{int N, Q, i;long long y1, y2, v;char s[7];scanf("%d%d", &N, &Q);for(i = 1; i <= N; i++) scanf("%I64d", &a[i]);build(1, 1, N); //建树memset(addv, 0, sizeof(addv));while(Q--){scanf("%s", s);if(s[0] == 'Q'){scanf("%I64d%I64d", &y1, &y2);_sum = 0;query(1, 1, N, y1, y2);printf("%I64d\n", _sum);}else{scanf("%I64d%I64d%I64d", &y1, &y2, &v);update(1, 1, N, y1, y2, v);}}return 0;
}