1.什么是树状数组

树状数组用来求区间元素和有着非常高的效率，求一次区间元素和的时间效率为O(logn)， 平常我们会遇到一些对数组进行维护查询的操作，常见的有修改某点的值、求某个区间的和，这两种是树状数组的强项！当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N)，如果实时的对数组进行M次修改或求和，最坏的情况下复杂度是O(M*N)，当规模增大后这是划不来的！而树状数组干同样的事复杂度却是O(M*lgN)。

2.树状数组图解

下图是树状数组非常经典的一张图(来自网络)

假设有一个数组A(下标从1开始，下标为0的空间一般不用），我们根据数组A得到数组C，从图中可以看出来：

C1 =A1
C2 =A1+A2
C3 =A3
C4 =A1+A2+A3+A4
C5 =A5
C6 =A5+A6
C7 =A7
C8 =A1+A2+A3+A4+A5+A6+A7+A8

推广到一般的，我们有以下公式：

1. i=17=00010001，最后一位第0位为1，代表的数值是 <nobr> 20=1 </nobr>,因此lowbit(17)=1，同样的道理，由于奇数的二进制表示，第0位总是1，因此对任意奇数，lowbit函数的返回值均为1。

2. i=16=00010000,第4位为1，代表的数值是 <nobr> 24=16 </nobr>,因此，lowbit(16)=16。同样的道理，对于可以表示为 <nobr> i=2m </nobr>的偶数i,lowbit函数的返回值均为其本身。

3. i=36=00100100,第2位为1，代表的数值是 <nobr> 22=4 </nobr>,因此，lowbit(36)=4。同样的道理，对于可以表示为 <nobr> i=y∗2m（y为奇数） </nobr>的偶数，lowbit函数的返回值为 <nobr> 2m </nobr>

3.lowbit函数实现

lowbit函数的实现如下：

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

实现的原理，在上一篇博文中已经有详细的介绍，在此不再赘述。

4.树状数组的构造

根据上面总结的公式，树状数组的构造可以用下列代码实现。

for(i=1;i<=N;i++)
        for(j=i-lowbit(i)+1;j<=i;j++)
        { c[i]+=a[j]; }

5.修改数组某一元素

如果修改了A数组中某一元素A[i]，那么相应的，C数组中某些元素也要做相应的修改。
对于上图，假设我们修改A[1]，将A[1]的值加3，那么相应的，我们需要将C[1]、C[2]、C[4]、C[8]的值分别加3。假如我们修改A[5],那么需要将C[5]、C[6]、C[8]的值分别加3。
我们使用下面的函数来实现对C数组的改变

void add(int i,int m)
{
    int j;
    for(j=i;j<=N;j+=lowbit(j))
    {
        c[j]+=m;
    }
}

6.求某一区间元素之和

我们使用下面的函数来计算从A[1]~A[i]的元素之和

int sum(int i)
{
    int sum = 0;
    while(i>0)
    {
        sum += c[i];
        i-=lowbit(i);
    }
    return sum;
}

对于任意一个数i，均可以表示为 <nobr> i=2m1+2m2+...+2mn−1+2mn </nobr>(m1>m2>….mn)