暴力超时，这道题可以用线段树做，因为更新的是单个节点，我们也可以用数组数组来做，我将两种方法的代码都给出
数组数组最适宜的用途就是区间求和和点的更新，但树状数组并不适用于区间的更新问题，也不是做不到，比较麻烦且难理解，有兴趣的可以看看这个http://blog.csdn.net/xindoo/article/details/8748410
//树状数组 #include<stdio.h> int n,ans[50005],f[50005]; int lowbit(int n) { return n&(-n); } void add(int i,int v) { while(i <= n) { ans[i] += v; i += lowbit(i); } } int query(int n) { int s = 0; while(n) { s += ans[n]; n -= lowbit(n); } return s; } int main() { int t; scanf("%d",&t); for(int j = 1;j <= t; j++) { scanf("%d",&n); for(int l = 1; l <= n;l++) { scanf("%d",&f[l]); f[l] += f[l-1]; } for(int l = 1; l <= n; l++) ans[l] = f[l]-f[l-lowbit(l)]; printf("Case %d:\n",j); while(1) { char s[20]; int a,b; scanf("%s",s); if (s[0] == 'E') break; scanf("%d%d",&a,&b); if (s[0] == 'A') add(a,b); if (s[0] == 'S') add(a,-b); if (s[0] == 'Q') printf("%d\n",query(b)-query(a-1)); } } return 0; }
//线段树解法 #include <stdio.h> #include <string.h> #define maxn 50005 struct node { int l, r, m; int sum; }tree[maxn<<2]; int a[maxn]; void build(int l, int r, int o) { tree[o].l = l; tree[o].r = r; int m = (l+r)>>1; tree[o].m = m; if (l == r) { tree[o].sum = a[l]; return; } build(l, m, o<<1); build(m+1, r, (o<<1)+1); tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum; } void update(int l, int v, int o) { tree[o].sum += v; if (tree[o].l == l && tree[o].r == l) return; if (l <= tree[o].m) update(l, v, o<<1); else update(l, v, (o<<1)+1); } int query(int l, int r, int o) { if (tree[o].l == r && tree[o].r == r) return tree[o].sum; if (tree[o].m >= r) return query(l, r, o<<1); else if (tree[o].m <l) return query(l, r, (o<<1)+1); else return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1); } int main() { int t, n; scanf("%d",&t); for (int j = 1; j <= t; j++) { scanf("%d",&n); for (int i = 1; i <= n; i++) scanf("%d",&a[i]); build(1, n, 1); printf("Case %d:\n",j); while(1) { char s[20]; int l, r; scanf("%s",s); if (s[0] == 'E') break; scanf("%d%d",&l,&r); if (s[0] == 'A') update(l, r, 1); else if (s[0] == 'S') update(l, -r, 1); if (s[0] == 'Q') printf("%d\n",query(l, r, 1)); } } return 0; }
