线段树 （区间更新，区间查询） poj http://poj.org/problem?id=3468

#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#include<string>using namespace std;const int N = 100005;typedef long long int LL;LL sum[N << 2];LL add[N << 2];struct node{ ???int l, r; ???int mid() ???{ ???????return (l + r) >> 1; ???}}tree[N << 2];void PushUp(int rt){ ???sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void PushDown(int rt, int m){ ???if (add[rt]) { ???????add[rt << 1] += add[rt]; ???????add[rt << 1 | 1] += add[rt]; ???????sum[rt << 1] += add[rt] * (m - (m >> 1)); ???????sum[rt << 1 | 1] += add[rt] * (m >> 1); ???????add[rt] = 0;//更新后要还原，因为递归可能会多次用到这个 ???}}void build(int l,int r,int rt){ ???tree[rt].l = l; ???tree[rt].r = r; ???add[rt] = 0; ???if (l == r) { ???????scanf("%lld", &sum[rt]); ???????return; ???} ???int m = tree[rt].mid(); ???build(l, m, rt << 1); ???build(m + 1, r, rt << 1 | 1); ???PushUp(rt); }void updata(int c, int l, int r, int rt){ ???if (tree[rt].l == l && r == tree[rt].r) { ???????add[rt] += c; ???????sum[rt] += (LL)(r - l + 1)*c; ???????return;//这里没有进行子区间更新，用到lazy标记 ???} ???if (tree[rt].l == tree[rt].r) return; ???PushDown(rt, tree[rt].r - tree[rt].l + 1); ???int m = tree[rt].mid(); ???if (r <= m) updata(c,l, r, rt << 1); ???else if (l > m) updata(c,l, r, rt << 1 | 1); ???else { ???????updata(c, l, m, rt << 1); ???????updata(c, m + 1, r, rt << 1 | 1); ???} ???PushUp(rt);}LL query(int l, int r, int rt){ ???if (l == tree[rt].l&&r == tree[rt].r) { ???????return sum[rt]; ???} ???PushDown(rt, tree[rt].r - tree[rt].l + 1);//标记的特点，用时才进行更新 ???int m = tree[rt].mid(); ???LL res = 0; ???if (r <= m) res += query(l, r, rt << 1); ???else if (l > m) res += query(l, r, rt << 1 | 1); ???else { ???????res += query(l, m, rt << 1); ???????res += query(m + 1, r, rt << 1 | 1); ???} ???return res;}int main(){ ???int n, m; ???while (scanf("%d %d", &n, &m) == 2) { ???????memset(sum, 0, sizeof(sum)); ???????memset(add, 0, sizeof(add)); ???????build(1, n, 1); ???????while (m--) { ???????????char ch[10]; ???????????scanf("%s", ch); ???????????if (ch[0] == ‘Q‘) { ???????????????int a, b; ???????????????scanf("%d %d", &a, &b); ???????????????printf("%lld\n", query(a, b, 1)); ???????????} ???????????else { ???????????????int a, b, c; ???????????????scanf("%d %d %d", &a, &b, &c); ???????????????updata(c, a, b, 1); ???????????} ???????} ???} ???return 0;}