一道经典的线段树区间更新的题，你值得拥有！
#include <cstdio> #define lchild rt << 1, l, m #define rchild rt << 1 | 1, m + 1, r const int maxn = 1 << 18; long long tree[maxn]; long long lazy[maxn]; int n; void push_up(int rt) { tree[rt] = tree[rt<<1] + tree[rt<<1|1]; } void push_down(int rt, int len) { tree[rt<<1] += lazy[rt] * (len - (len >> 1)); lazy[rt<<1] += lazy[rt]; tree[rt<<1|1] += lazy[rt] * (len >> 1); lazy[rt<<1|1] += lazy[rt]; lazy[rt] = 0; } void build(int rt = 1, int l = 1, int r = n) { if (l == r) { scanf("%lld", &tree[rt]); return; } int m = (l + r) >> 1; build(lchild); build(rchild); push_up(rt); } void update(int L, int R, int delta, int rt = 1, int l = 1, int r = n) { if (L <= l && r <= R) { tree[rt] += delta * (r - l + 1); lazy[rt] += delta; return; } if (lazy[rt]) { push_down(rt, r - l + 1); } int m = (l + r) >> 1; if (L <= m) { update(L, R, delta, lchild); } if (R > m) { update(L, R, delta, rchild); } push_up(rt); } long long query(int L, int R, int rt = 1, int l = 1, int r = n) { if (L <= l && r <= R) { return tree[rt]; } if (lazy[rt]) { push_down(rt, r - l + 1); } int m = (l + r) >> 1; long long ret = 0; if (L <= m) { ret += query(L, R, lchild); } if (R > m) { ret += query(L, R, rchild); } return ret; } int main(int argc, char const *argv[]) { int q; scanf("%d%d", &n, &q); build(1, 1, n); for (int i = 0; i < q; i++) { getchar(); int ch; if ((ch = getchar()) == 'Q') { int x, y; scanf("%d%d", &x, &y); printf("%lld\n", query(x, y)); } else { int x, y, z; scanf("%d%d%d", &x, &y, &z); update(x, y, z); } } return 0; }