线段树通用的几个函数：
build()（建树）、pushup()（更新父节点）、pushdown()（用到lazy标记时使用）
其他的单点更新、区间更新以及返回区间值等等，其内部代码原理都是差不多的。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 50010; struct stuff{ int l,r,sum; }sum[maxn<<2]; int add[maxn]; char str[6]; void push(int rt) { sum[rt].sum = sum[rt<<1].sum + sum[rt<<1|1].sum; } void build(int l,int r,int rt) { sum[rt].l = l; sum[rt].r = r; if(l==r) sum[rt].sum = add[l]; else { int m = (l+r)/2; build(l,m,rt<<1); build(m+1,r,rt<<1|1); push(rt); } } void Add(int rt, int c, int x) { if(sum[rt].l == x && sum[rt].r == x) { sum[rt].sum += c; } else { int m = (sum[rt].l + sum[rt].r)/2; if(m >= x) Add(rt<<1,c,x); else Add(rt<<1|1,c,x); push(rt); } } void sub(int rt, int c,int x) { if(sum[rt].l == x && sum[rt].r == x) { if(sum[rt].sum <= c) sum[rt].sum = 0; else sum[rt].sum -= c; } else { int m = (sum[rt].l + sum[rt].r)/2; if(m >= x) sub(rt<<1,c,x); else sub(rt<<1|1,c,x); push(rt); } } int query(int rt, int l, int r) { if(sum[rt].l >= l && sum[rt].r <= r) { return sum[rt].sum; } else { int ans = 0; int m = (sum[rt].l + sum[rt].r)/2; if(m >= l) ans += query(rt<<1,l,r); if(m < r) ans += query(rt<<1|1,l,r); return ans; } } int main() { int n,t,cas = 1; scanf("%d", &t); while(t--) { memset(sum,0,sizeof(sum)); scanf("%d", &n); int i,j; for(i=1; i<=n; i++) { scanf("%d", &add[i]); } build(1,n,1); printf("Case %d:\n", cas); while(scanf("%s", str),strcmp(str, "End")) { scanf("%d%d", &i,&j); if(strcmp(str, "Add") == 0) { Add(1,j,i); } else if(strcmp(str, "Query") == 0) { cout << query(1,i,j) << endl;; } else if(strcmp(str, "Sub") == 0) { sub(1,j,i); } } cas++; } return 0; }
