http://acm.hdu.edu.cn/showproblem.php?pid=1166
题解:
此题用树状数组来做,其操作为给某一个兵营增加或减少人数,以及询问i~j营地的人数,可以用树状数组维护前i个营地的人数总数,通过前j个营地的人数的总数减去前i-1个营地的人数总数就得到了i~j营地的总人数了。
#include <iostream> #include <bits/stdc++.h> using namespace std; const int maxn=50005; int s[maxn],n; int lowbit(int k) { return k&(-k); } void add(int k,int v)//向第k个营地增加v个人 { while(k<=n) { s[k]+=v; k+=lowbit(k); } } int sum(int k) { int re=0; while(k>0) { re+=s[k]; k-=lowbit(k); } return re; } int main() { int t,ca=1; char op[10]; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(s,0,sizeof(s)); for(int i=1;i<=n;i++) { int num; scanf("%d",&num); add(i,num); } printf("Case %d:\n",ca++); int i,j; while(scanf("%s",op)&&op[0]!='E') { scanf("%d %d",&i,&j); if(op[0]=='Q') { printf("%d\n",sum(j)-sum(i-1)); }else if(op[0]=='S') { add(i,-j); }else if(op[0]=='A') { add(i,j); } } } return 0; }