一、树状数组

     树状数组可以在logn的时间内求出一段连续区间的和，特别对于多次修改后再求值，树状数组就显得尤为重要了。
定义原数组A[i],1<=i<=n  定义数组C[i]，则有：

由此联想到二进制，树状数组的每一项是原数组几项的和，至于是多少项，这和i的二进制数从右向左数0的个数有关，例如4是100，从右向左2个0，那么就是2^2=4，有四项，
再如6=110，2^1=2，有2项。
如何求这个项数呢？
有个简单的方法   i&(-i)
简单解释下，我们举个5吧，5的二进制是0000 0101   ，在计算机中，负数是根据其相反数的补码+1决定的，所以-5就是1111 1011  所以5&(-5)就是1
更新：
    原数组第i项最早出现在树状数组的第i项，但是，由于后面其他项也包含了原数组的第i项，所以更新操作是
    
for(int i=x;i<=maxn;i+=lowbit(i))
{
	C[i]+=val;
}
比如修改原来的第1项，那么对应修改树状数组的1,2,4,8，.....
求和：

    和第i项有关的项都在前面，所以求和操作就是
for(int i=x;i;i-=lowbit(i))
{
    ans+=tree[i];
}

比如求前11项的和，转换为C[11]+C[10]+C[8]，这样就不会漏项了。



注意：

    树状数组一定从第一项开始，所以在做题的时候一样要注意原数组的开始位置。





二、二维树状数组
给定一个矩阵，然后会修改某个值，再问你某个子矩阵的和
其实也很容易，同样的定义一个树状数组C[][]
则有：


其实就是行和列上都来一次树状数组，对于第i行的，根据lowbit(i)包含前面的项，对于第j列的，其实和一维树状数组一样了。

更新：
   
void add(int x,int y)
{
    for (int i=x;i<=N;i+=lowbit(i))
        for (int j=y;j<=N;j+=lowbit(j))
            C[i][j]++;


求和：

int sum(int x,int y)                      
{                                         
    int ans=0;                            
    for (int i=x;i;i-=lowbit(i))          
        for (int j=y;j;j-=lowbit(j))      
            ans+=tree[i][j];              
    return ans;                           
}                                         



感想

巧妙地利用树状数组，可以解决很多问题，而且其效率也很高，是一种很神奇的数据结构，树状数组灵活多变，个人认为活学活用还是挺有难度的......多做题，争取提高这方面的能力吧！