题意：
有n个数，有m组操作，1 i表示将第i个数先输出，然后置0， 2 i v 表示给第i个数加上v， 3 i j 表示求i 到 j 的和，注意，这里数组是从0开始的，而我们构造的树状数组是从1
开始的，使用在程序中要进行一定的处理。
//LA 1112 - Curious Robin Hood(树状数组) //2013-04-13-08.22 #include <stdio.h> #include <string.h> const int maxn = 100010; int a[maxn], b[maxn]; int n; int lowbit(int x) { return x&(-x); } void update(int x, int v) { while (x <= n) { a[x] += v; x += lowbit(x); } } int getsum(int x) { int sum = 0; while (x) { sum += a[x]; x -= lowbit(x); } return sum; } int main() { int t, m; scanf("%d",&t); for (int k = 1; k <= t; k++) { scanf("%d %d",&n, &m); memset(a, 0 ,sizeof(a)); for (int i = 1; i <= n; i++) { scanf("%d",&b[i]); update(i, b[i]); } int op, i, v, j; printf("Case %d:\n",k); while (m--) { scanf("%d",&op); if (op == 1) { scanf("%d",&i); printf("%d\n",b[i+1]); update(i+1, -b[i+1]); b[i+1] = 0; } else if (op == 2) { scanf("%d %d",&i, &v); update(i+1, v); b[i+1] += v; } else { scanf("%d %d",&i,&j); printf("%d\n",getsum(j+1) - getsum(i)); } } } return 0; }
