HDU 1166 敌兵布阵

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; }