Description
给出了一个序列，你需要处理如下两种询问。
"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。
"Q a b" 询问[a, b]区间中所有值的和。
Input
第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.
第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。
接下来Q行询问，格式如题目描述。
Output
对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15 这个题搞了不少时间，主要是难懂，而且写代码稍微快一点就 各种错误，吓得我不敢写快了，以后还是要多多细心才行。 这道题用开始那种线段树已经不行了，必须想出效率更高的方法，于是延迟标记出来了，用sign数组表示，它主要用于记录目前更新或者查询到的节点，并且它很懒，不更新未到节点，直到某次查询或者更新到标记的节点的子节点时
这个时候就把当前节点更新了，去掉节点标记时需要把子节点标记。 此次代码重点：区间更新，延迟标记
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std; #define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 const int MX = 100050;
long long sum[MX<<2];
long long sign[MX<<2];
int T, n, Q, X, Y;
long long Z; void PushUp(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(int rt, int len) {
if (sign[rt]) {
sign[rt<<1] += sign[rt];
sign[rt<<1|1] += sign[rt];
sum[rt<<1] += (len - (len>>1)) * sign[rt];//为了解决奇数所带来的子节点分配不平衡问题，因此需要这样做
sum[rt<<1|1] += (len>>1) * sign[rt];
sign[rt] = 0;
}
}
void Build(int l, int r, int rt) {
sign[rt] = 0;//初始化标记
if (l == r) {
scanf("%lld", &sum[rt]);
return ;
}
int m = (l + r)>>1;
Build(lson);
Build(rson);
PushUp(rt);
}
void Update(int L, int R, long long z, int l, int r, int rt) {
if (L <= l && r <= R) {
sign[rt] += z;//记录下更新的值
sum[rt] += z * (r - l + 1);//批量更新
return ;
}
PushDown(rt, r - l + 1);//检查标记，看是否需要继续向下更新
int m = (l + r)>>1;
if (L <= m) Update(L, R, z, lson);
if (R > m) Update(L, R, z, rson);
PushUp(rt);
}
long long Query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
PushDown(rt, r - l + 1);//别忘了查询时也要注意标记是否存在
int m = (l + r)>>1;
long long ret = 0;
if (L <= m) ret += Query(L, R, lson);
if (R > m) ret += Query(L, R, rson);
return ret;
}
int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%d %d\n", &n, &Q) != EOF) {
Build(1, n, 1);
while (Q--) {
char op[2];
scanf("%s", op);
if (op[0] == 'Q') {
scanf("%d %d", &X, &Y);
long long ans = Query(X, Y, 1, n, 1);
printf("%lld\n", ans);
} else {
scanf("%d %d %lld", &X, &Y, &Z);
Update(X, Y, Z, 1, n, 1);
}
}
}
return 0;
}