题意 ：HDU的中文题也不常见。。。。这道题我就不详述了。。。。。
思路 ：这个题用线段树用树状数组都可以，用线段树的时候要注意输入那个地方，输入一个字符串的时候不要紧接着输入两个数字，因为我就是这样贡献了好几个RE。。。。
树状数组也不要用cin，cout，因为也是这样我又贡献了好几个TLE。。。。血一般的教训啊，这道题是水题，模板题。
这个是线段树的代码
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> using namespace std; const int maxn = 500005 ; int a[maxn] ; int ans ; struct node { int l,r,value ; } Node[4*maxn] ; void build(int v ,int l,int r) { Node[v].l = l ; Node[v].r = r ; if(l == r) { Node[v].value = a[r] ; return ; } int mid = (l+r)>>1 ; build(v*2,l,mid) ; build(v*2+1,mid+1,r) ; Node[v].value = Node[v*2].value+Node[v*2+1].value ; } int query(int v,int l,int r) { if(Node[v].l == l && Node[v].r == r) return Node[v].value ; int mid = (Node[v].l+Node[v].r) >> 1 ; if(r <= mid) return query(v*2,l,r) ; else { if(l > mid) return query(v*2+1,l,r) ; else return query(v*2,l,mid)+query(v*2+1,mid+1,r) ; } } void update(int v,int n,int m) { Node[v].value += m ; if(Node[v].l == n && Node[v].r == n) return ; else { int mid = (Node[v].l+Node[v].r)>>1 ; if(n <= mid) update(2*v,n,m) ; else if(n > mid) update(2*v+1,n,m) ; } } void sub(int v,int n,int m) { Node[v].value -= m ; if(Node[v].l == n && Node[v].r == n) return ; else { int mid = (Node[v].l+Node[v].r)>>1 ; if(n <= mid) sub(2*v,n,m) ; else if(n > mid) sub(2*v+1,n,m) ; } } int main() { int T ,x=1; scanf("%d",&T) ; while(T--) { int n ; ans = 0; scanf("%d",&n) ; for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]) ; build(1,1,n) ; printf("Case %d:\n",x++) ; char ch[31] ; while(true) { scanf("%s",ch) ; int a,b ; if(ch[0] == ‘Q‘) { scanf("%d %d",&a,&b) ; printf("%d\n",query(1,a,b)) ; } else if(ch[0] == ‘A‘){ scanf("%d %d",&a,&b) ; update(1,a,b) ; } else if(ch[0] == ‘S‘){ scanf("%d %d",&a,&b) ; sub(1,a,b) ; } if(ch[0] == ‘E‘) break ; } // printf("\n") ; } return 0; }
这个是树状数组的
#include <stdio.h> #include <iostream> #include <string.h> using namespace std ; const int maxn = 500003 ; int ch[maxn] ; int data ; int n ; int lowbit(int i) { return i&(-i) ; } int sum(int i) { int ans = 0 ; while(i > 0) { ans += ch[i] ; i -= lowbit(i) ; } return ans ; } void add(int x,int value) { while(x <= n) { ch[x] += value ; x += lowbit(x) ; } } int main() { int T ; scanf("%d",&T) ; for(int i = 1 ; i <= T ; i++) { scanf("%d",&n) ; memset(ch,0,sizeof(ch)) ; for(int j = 1 ; j <= n ; j++) { scanf("%d",&data) ; add(j,data) ; } printf("Case %d:\n",i) ; char sh[31] ; int a,b ; while(~scanf("%s",sh)) { if(sh[0] == ‘E‘) break ; if(sh[0] == ‘A‘) { scanf("%d %d",&a,&b) ; add(a,b) ; } if(sh[0] == ‘Q‘) { scanf("%d %d",&a,&b) ; printf("%d\n",sum(b)-sum(a-1)) ; } if(sh[0] == ‘S‘) { scanf("%d %d",&a,&b); add(a,-b) ; } } } return 0 ; }
原文：http://www.cnblogs.com/luyingfeng/p/3558223.html
