lowbit函数
这里我们先不管树状数组这种数据结构到底是什么，先来了解下lowbit这个函数，你也先不要问这个函数到底在树状数组中有什么用；

顾名思义，lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1，举个例子，x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2。

那么怎么求lowbit呢？

还记得 剑指Offer66题之每日6题 - 第二天中的第五题中讲过的如何消掉最后一位1吗？我们就是先消掉最后一位1，然后再用原数减去消掉最后一位1后的数，答案就是lowbit(x)的结果；

第二种方法就是计算机组成原理课上老师教过我们求负数的补码的简便方法：把这个数的二进制写出来，然后从右向左找到第一个1(这个1就是我们要求的结果，但是现在表示不出来，后来的操作就是让这个1能表示出来)，这个1不要动和这个1右边的二进制不变，左边的二进制依次取反，这样就求出的一个数的补码，说这个方法主要是让我们理解一个负数的补码在二进制上的特征，然后我们把这个负数对应的正数与该负数与运算一下，由于这个1的左边的二进制与正数的原码对应的部分是相反的，所以相与一定都为0,；由于这个1和这个1右边的二进制都是不变的，因此，相与后还是原来的样子，故，这样搞出来的结果就是lowbit(x)的结果。

两种方法对应的代码依次如下：

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

树状数组的思想
在树状数组的问题模型中已经有所提及了，就是那两种不同做法的一个综合；

先定义一些东西：arr是原数组，c是新开的一个数组，这个数组代表后缀和(问题模型中是用的前缀和，这里要用后缀和，具体原因马上就知道了)；

二进制的视角：一个数n，假设n = 6，它的二进制为110，我们把它表示成累加的形式110 = 100 + 10，这样是可以的，那么我们要求前6(110)项的和是不是可以这样求：
∑i=16=(arr1+arr2+arr3+arr4)+(arr5+arr6)

注意括号中的元素个数，是不是4(100)个加2(10)个，和110 = 100 + 10是不是很像，不知你们发现了吗，10就是lowbit(110)的结果，100是lowbit(100)的结果。求和的时候我们总是把∑ni=1∑i=1n拆分成这样的几段区间和来计算，而如何去确定这些区间的起点和长度呢？就是根据n的二进制来的(不懂的可以再看下上面举的例子)，二进制怎么拆的，你就怎么拆分，而拆分二进制就要用到上面说的lowbit函数了。这里也可以顺理成章得给出c数组的表示了。

这里也可以顺理成章得给出c数组的表示了，c[i]表示从第i个元素向前数lowbit(i)个元素，这一段的和，这就是上面说的区间和，只不过这个区间是靠右端点的；你可能又会想，不是说区间是靠右端点的吗，是后缀和啊，那中间的这些区间怎么定义？其实递归定义就好了，比如说

∑6i=1=(arr1+arr2+arr3+arr4)+(arr5+arr6)=∑6i=1=(arr1+arr2+arr3+arr4)+c[6]∑i=16=(arr1+arr2+arr3+arr4)+(arr5+arr6)=∑i=16=(arr1+arr2+arr3+arr4)+c[6]，你把c[6]去掉，不就是∑4i=1=(arr1+arr2+arr3+arr4)∑i=14=(arr1+arr2+arr3+arr4)，这个区间不就靠右端点了吗，∑4i=1=c[4]=c[6−lowbit(6)]∑i=14=c[4]=c[6−lowbit(6)]。

其实你把所有的数字都看成二进制，很好理解的。

树状数组的实现
设计一种数据结构，需要的操作无非就是”增删改查“，这里只讨论查询和修改操作具体是怎么实现的；

查询
这里说的查询是查询任一区间的和，由于区间和具有可加减性，故转化为求前缀和；

查询前缀和刚刚在树状数组的思想中已经说过了，就是把大区间分成几段长度不等的小区间，然后求和。区间的个数为O(logn)O(logn)，所以查询的时间复杂度为O(logn)O(logn)。

修改
修改某一位置上的元素的时间复杂度为O(1)O(1)，但是要更新c数组，不然查询的时间复杂度就会变高。更新的方法就要提一下树状数组的性质了和树状数组那张经典的图片了。

这张图片中已经把c数组的后缀和这个含义已经表达得很清楚了。这个时候你再把查询操作对应到这张图上，然后看着二进制来操作，是不是就可以很直白地理解上面所说的查询操作了！

我们从这张图中可以得到树状数组的如下性质：

后缀和的长度是2的幂；
上一层后缀和的长度是下一层后缀和长度的两倍；
下一层后缀和只要补上自己后缀和的长度就可以得到上面层的后缀和(图中的虚框框)，注意，是上面的后缀和，而不是上一层的后缀和，这个性质就是更新操作的依据；
最后一位1右边有多少个0(可以用log2(lowbit(x))log2(lowbit(x))表示)就表示这一层有多少个直系子层(子层的意思就是这一层的和包含下面某一层的和)。
我暂时就写这么多吧，这个时候我们再来说更新操作；

更新的时候只要更新修改这个点会影响到的那些后缀和(c数组)，假设现在修改6(110)这个点，依据树状数组的性质三，它影响的直系父层就是c[6(110) + lowbit(6(110))] = c[8(1000)]，但是它肯定不是只影响直系父层，上面所有包含这一层和的层都要更新，但是我们把这个更新传递给直系父层c[8],8这个点的直系父层是c[16]，依次类推地更新就行了。

这里我留一个问题给大家，如何寻找某一层的所有直系子层，大家可以看这个图思考一下，想一想。

树状数组的代码
 

查询前缀和
int sum(int x, ArrayInt c, int n)
{
    int ret = 0;
    for ( ; x > 0; ret += c[x], x -= lowbit(x));
    return ret;
}

更新后缀和
void update(int x, int val, ArrayInt c, int n)
{
    for ( ; x <= n; c[x] += val, x += lowbit(x));
}