最基本的线段树的区间更新及查询和
用tag(lazy)数组来“延缓”更新，查询或添加操作必须进行pushdown操作，即把tag从p传到lp和rp并清楚tag[p]，既然得往lp和rp递归，那么就可以“顺便”往下传
pushdown操作代码
inline void pushdown(int p, int llen, int rlen) {
if (tag[p]) {
tag[lp] += tag[p], tag[rp] += tag[p];
tree[lp] += tag[p] * llen;
tree[rp] += tag[p] * rlen;
tag[p] = ;
}
}
还要注意必须用long long来存值
代码如下
#include <cstdio>
#include <algorithm>
#define ll long long
#define lp p<<1
#define rp p<<1|1
using namespace std; const int maxn = ;
ll tree[maxn<<], tag[maxn<<];
void build(int p, int l, int r) {
if (l == r) {
scanf("%lld", &tree[p]);
return;
}
int mid = (l + r) >> ;
build(lp, l, mid); build(rp, mid + , r);
tree[p] = tree[lp] + tree[rp];
}
inline void pushdown(int p, int llen, int rlen) {
if (tag[p]) {
tag[lp] += tag[p], tag[rp] += tag[p];
tree[lp] += tag[p] * llen;
tree[rp] += tag[p] * rlen;
tag[p] = ;
}
}
void add(int p, int l, int r, int x, int y, int z) {
if (x <= l && y >= r) {
tag[p] += 1LL * z;
tree[p] += 1LL * z * (r - l + );
return;
}
int mid = (l + r) >> ;
pushdown(p, mid - l + , r - mid);
if (x <= mid) add(lp, l, mid, x, y, z);
if (y > mid) add(rp, mid + , r, x, y, z);
tree[p] = tree[lp] + tree[rp];
} ll find(int p, int l, int r, int x, int y) {
if (x <= l && y >= r) return tree[p];
int mid = (l + r) >> ;
pushdown(p, mid - l + , r - mid);
if (y <= mid) return find(lp, l, mid, x, y);
if (x > mid) return find(rp, mid + , r, x, y);
return find(lp, l, mid, x, y) + find(rp, mid + , r, x, y);
} int main() {
int n, q;
scanf("%d%d", &n, &q);
build(, , n);
while (q--) {
char s[];
int x, y;
scanf("%s%d%d", s, &x, &y);
if (s[] == 'Q') {
printf("%lld\n", find(, , n, x, y));
} else {
int z; scanf("%d", &z);
add(, , n, x, y, z);
}
}
return ;
}