HDU 1166 敌兵布阵(树状数组入门)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

        之前用线段树写这种题感觉太麻烦了，代码太长了还容易有bug，但是有了树状数组既能省空间和时间，代码也不是很长，可以缩短你的ac时间。至于树状数组的详解看下别人的博客吧，讲的都很清楚，主要是对lowbit的加减操作的理解，感觉这个还是挺简单的...

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 50005
using namespace std;
int T,n;
int pre[maxn];
string ch;

int lowbit(int x){return x & (-x);}

void add(int x,int y){
  for(int i=x;i<=n;i+=lowbit(i)){
    pre[i] += y;
  }
}

void Update(int x,int y){
  for(int i=x;i<=n;i+=lowbit(i)){
    pre[i] += y;
  }
}

int Query(int x){
  int sum = 0;
  for(int i=x;i>=1;i-=lowbit(i)){
    sum += pre[i];
  }
  return sum;
}

int main()
{
  int Case = 1;
  scanf("%d",&T);
  while(T--){
    scanf("%d",&n);
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++){
      int index;
      scanf("%d",&index);
      add(i, index);
    }
    printf("Case %d:\n",Case++);
    while(cin>>ch){
      if(ch == "Query"){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",Query(y) - Query(x-1));
      }
      else if(ch == "Add"){
        int x,y;
        scanf("%d%d",&x,&y);
        Update(x,y);
      }
      else if(ch == "Sub"){
        int x,y;
        scanf("%d%d",&x,&y);
        Update(x,-y);
      }
      else break;
    }
  }
  return 0;
}