树状数组的引入：

对于查询和修改要求差不多，使用树状数组可以达到logN的复杂度

红色矩形表示的数组C就是树状数组.这里,C[i]表示A[i-2^k+1]到A[i]的和,而k则是i在二进制时末尾0的个数，或者说是i用2的幂方和表示时的最小指数。

所谓的k，也是该节点在树中的高度.

修改第i个元素，为了维护数组C的意义，需要修改C[i]以及C[i]的全部祖先，而非C[i]的祖先的节点则对于第i个元素的修改，不会发生改变。祖先共有“树的高度 - C[i]节点高度”个

要求区间[p,q]元素和，可求[1,q]、[1,p]作差。则问题转化为如何查询一个区间[1,p]的元素和，即求s[p]。对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可
实现树状数组的关键，在于求一个数p的二进制时末尾0的个数k（用2的幂方和表示时的最小指数）。而2^k就是修改（和统计）时指针滑动的距离，我们定义这个值为p的lowbit。
        更具体的说，正整数p的lowbit为将p二进制中最后一个1按位抽取的结果。
比如，23（10111）的lowbit为1（00001），20（10100）的lowbit为4（00100）。

lowbit(p) = p & ( p ^ ( p - 1 ) )
        
根据有符号整数的补码规则，我们可以发现(p^(p-1))恰好等于-p,即lowbit的求取公式可以更为简练：
lowbit(p) = p & -p

void plus(int x, int num)
{
	while ( x <= n)
	{
		c[ x ] += num;
		x += lowbit( x );
	}
}int sum(int x){    int s = 0;    while ( x )    {        s += c[ x ];        x -= lowbit( x );    }    return s;}//敌兵布阵#include<cstdio>#include<algorithm>#include<queue>#include<stack>using namespace std;int T;int N;int a[500010];int lowbit(int x){    return x&(-x);}void update(int x,int num){    while(x<=N)    {        a[x]=a[x]+num;        x=x+lowbit(x);    }    }int query(int x){    int ans=0;    while(x>0)    {        ans+=a[x];        x-=lowbit(x);    }    return ans;}int main(){    //freopen("D:\\out.txt","w",stdout);    int i,j,k;    char str[100],tmp[10];    scanf("%d",&T);    k=1;    while(T--)    {        scanf("%d",&N);        memset(a,0,sizeof(a));        for(i=1;i<=N;i++)        {            scanf("%d",&j);            update(i,j);        }        printf("Case %d:\n",k++);        while(1)        {            scanf("%s",str);            if(str[0]=='E')                break;            scanf("%d%d",&i,&j);            if(str[0]=='A') update(i,j);            if(str[0]=='S') update(i,-j);//使用-号就可以了...            if(str[0]=='Q') printf("%d\n",query(j)-query(i-1));//注意这里是i-1，因为树状数组都是闭区间        }    }    return 0;} 

HDU 1166 敌兵布阵 （树状数组入门）