前言
在数组，我们常常会遇上区间求和相关的问题，即求数组A中第i个元素到第j个元素(i<j)之和。
这个问题看起来比较简单，只需要累加即可：
$$Sum(i,j) = A[i]+A[i+1]+...+A[j]$$
但是在面对大数据量的时候，它的时间复杂度也很高，而且如果需要进行多次查询，我们可能会进行大量重复的计算，这时一种效率上的浪费。
那有的同学可能会想到，如果要区间求和，可以使用前缀和数组啊，我们用S[i]记录第一个元素到第i个元素之和，那么做差不就可以得到区间和了吗？
$$Sum(i,j) = S[j]-S[i-1]$$
如果这个数组是一个常量，那么用前缀和数组确实完事大吉了，可是万一数组要更新呢，假如元素A[x]要更新，那个从第x个元素开始，所有S数组的值都要改变，这又带来了很多时间上的开销。相比之下，前一种方法就简单多了，只需要更新A[x]即可。
| 区间求和 | 更新元素 | |
| 累加求和 | O(n) | O(1) |
| 前缀数组 | O(1) | O(n) |
由此可见，累加求和和前缀和数组各有缺陷，我们需要一种新的数据结构和算法，既能高效地查询区间之和，更新元素时又比较方便。于是乎，树状数组就出现了。
树状数组是被应用于区间相关计算的经典数据结构，它巧妙地运用了二进制，提升了区间求和，元素更新的效率。
树状数组和二进制
设树状数组为C,其元素C[i]和前缀和数组S[i]一样，记录的也是到第i个元素为止，原数组部分元素的和，但是到底是几个元素的和，就要看i的二进制表示了。我们要找到下标转化为二进制中最后一个1位置，以此来确定树状数组所覆盖的原数组的长度，所以也可以看出，C[i]所覆盖数组的长度，也就是能整除i的最大2的幂次。这么说可能比较抽象，我们来举几个例子，假设树状数组为C，求C[14],C[15],C[16]各自覆盖的元素的长度，现将其转化为二进制：
14最后一个1出现在倒数第二位，那么它覆盖的原数组的长度就是2^1 = 2,15最后一个1出现在倒数第一位，那么它覆盖的原数组的长度就是2^0 = 1,16最后一个1出现在第一位，那么它覆盖的原数组的长度就是2^5 = 16。
用一张图来比较树状数组和原数组
区间求和
从上图可以看见，树状数组通过二进制，用一个数组表示多个不同长度的部分和。这样，在计算前缀和时，只需要挑选合适的值组合在一起就好了，例如,前11个元素之和即为：
$$Sum(1,11) = C[11]+C[10]+C[8]$$
如果采用累加求和的方式，需要进行10次加法运算，但是使用树状数组，就只需要两次加法运算，计算量大大降低了，如果要求区间之和，只需要求前缀和之差就可以了。
单点更新
当原数组元素更新时，树状数组的对应元素也要跟着一同更新，但它和前缀和不同，只需要更新部分值。 具体来说，就是树状数组中那些涵盖了更新元素的值。例如，当原数组A[5]更新时，涵盖它的C[5],C[6],C[8],C[16]都要同步更新。同用是更新，前缀和数组需要更新12个元素。
代码实现
从之前的分析可以看出，使用树状数组可以同时提高区间求和和单点更新的效率，但是我们还有很多细节性的问题没有解决，其中最重要的就是两点：
- 更新原数组时，树状数组中哪些元素要跟着更新呢？
- 区间求和时，该如何选择对应的元素呢？
下面就来揭晓这些问题的答案。首先，回到最初的问题，假设数组下标为x，我们说要找到x二进制中最后一个1的位置，以确定树状数组所覆盖的部分和长度，这该如何实现呢？这里其实要用到位运算，设lowbit(x)为取x最后一个1对应的2的幂次，有:
$ lowbit(x) = x&(-x) $
在计算机中，整数x取反相当于把x二进制的每一位都取反，然后加1，所以-x和x的最后一个1的位置相同，其他所有1的位置均不同，然后两者按位与，即可得到最后一个1的位置：
确定了这个最低位1的位置,问题就清晰很多了，我们知道,C[i]代表到A[i]为止之前(包括A[i])，lowbit(i)个元素之和。这样就可以将A[i]至A[i]之和分为两部分，从而可以缩小问题规模:
$$Sum(1,i) = Sum(1,i-lowbit(i))+C[i]$$
对应的代码也不难得到：
1 int getSum(int x){
2 int sum = 0;
3 for(int i=x;i>0;i-=lowbit(i)){
4 sum+=C[i];
5 }
6 return sum;
7 }
求区间和Sum(i,j),只要作差即可：
$$Sum(i,j) = Sum(1,j)-Sum(1,i-1)$$
下面解决另一个关键问题，当原数组A有元素更新时，树状数组C要如何更新呢？很明显，当A[i]更新时，C必定是从C[i]处开始更新(C[i]之前没有覆盖到A[i])。如果C[i]被更新，那么之后i之后，覆盖C[i]的元素也一定会更新，实际上，这种更新时逐层的，例如更新C[3]会导致C[4]更新，C[4]更新导致C[8]更新。因此，若已知C[i]被更新，则C中下一个被更新的元素是离C[i]最近，覆盖了C[i]的值。设这个元素在i之后第a位，即C[i+a],若C[i+a]可以覆盖C[i]中的元素，则必须满足，C[i+a]覆盖的第一个A中元素的下标小于等于都C[i]覆盖的第一个A中元素的小标，即：
$$i+a-lowbit(i+a)<=i-lowbit(i)\\a<=lowbit(i+a)-lowbit(i)$$
这样，该问题就变成了，求满足上式最小的a。
思考lowbit函数的定义，我们可以发现，a不可能比lowbit(i)小，否则i+a二进制中最后一个1的位置一定在中最后一个1的后面，lowbit(i+a)-lowbit(i)<0。那a可以取lowbit(i)吗，可以的。因为i+lowbit(i)最后一个1的位置相同，两种相加会导致进位，只要进位，就等于两个lowbit(i)之和了，所以
$$lowbit(i)<=lowbit(i+a)-lowbit(i)\\lowbit(i)+lowbit(i)<=lowbit(i+lowbit(i))$$
所以a取lowbit(i)。
更新代码如下：
1 void updata(int x,int v) //将第x个整数加上v
2 {
3 for(int i=x;i<=N;i+=lowbit(i)){
4 c[i]+=v;
5 }
6 }