【树状数组初探第二弹】HDU 1166题解——敌兵布阵
来源：点击打开链接
这个题有两种解法，树状数组&线段树，当然这也是这种题目的通常状况，线段树和划分树普适性更强一些，但线段树显然更简单，比如我印象深刻的有2012长春赛区区域网络赛的第一道题，快速的做法是用一个三维的树状数组，无解的怨念啊。。
这个题没什么要注意的，寻找第I到J个的和也很简单，用find_add(J)-find_add(I-1)就行了。。。。这两道题很适合初学者了解树状数组。
感觉最主要的便是神奇的lowbit函数了，类似的讲解网上遍地都是，不多说了。。
#include <iostream>#include <stdio.h>#include <cstring>using namespace std;int c[50005];int N;int lowbit(int x){return x&(-x);}int query_add(int x){int result=0;for(int i=x;i>0;i-=lowbit(i)){result+=c[i];}return result;}void modify_add(int pos,int delta){for(int i=pos;i<=N;i+=lowbit(i)){c[i]+=delta;}}void modify_sub(int pos,int delta){for(int i=pos;i<=N;i+=lowbit(i)){c[i]-=delta;}}int main(){int testcase;char a[30];scanf("%d",&testcase);for(int p=1;p<=testcase;p++){memset(c,0,sizeof(c));int packnum,x,y;scanf("%d",&packnum);N=packnum;for(int i=1;i<=packnum;i++){int temp;scanf("%d",&temp);modify_add(i,temp);}printf("Case %d:\n",p);while(true){scanf("%s",&a);if(a[0]=='E')break;else if(strcmp("Query",a)==0){scanf("%d%d",&x,&y);printf("%d\n",query_add(y)-query_add(x-1));}else if(strcmp("Add",a)==0){scanf("%d%d",&x,&y);modify_add(x,y);}else if(strcmp("Sub",a)==0){scanf("%d%d",&x,&y);modify_sub(x,y);}}}return 0;}