前缀和数组：
初始化：O(n)时间复杂度，顺序扫描原数组即可
查询区间和：O(1)时间复杂度，S[j]-S[i]即为原数组i到j的区间和
单点修改：O(n)时间复杂度，需要修改S[i]~S[n]所有值，单点修改效率低

改进：
引出本文的主角：树状数组。 先看一个重要概念：

lowbit函数

定义：lowbit(i)代表i这个数字，二进制表示的最后一位1的位权
例如：
lowbit(8)=(1000)2 =8
lowbit(6)=(110)2=4
lowbit(12)=(1100)2=4
lowbit(7)=(111)2=1
计算公式：lowbit(x)=x&(-x)
对于这个公式的理解：
我们知道,对于一个数的负数的二进制表示使用补码，补码就等于对这个数取反+1
以二进制数11010为例:11010的补码为00101,加1后为00110,两者相与便是最低位的1
其实很好理解,补码和原码必然相反,所以原码有0的部位补码全是1,补码再+1之后由于进位那么最末尾的1和原码
最右边的1一定是同一个位置(当遇到第一个1的时候补码此位为0,由于前面会进一位,所以此位会变为1)

树状数组

定义：c[i]表示前lowbit(i)项的和
图片.png
例如：lowbit(8)=8 c[8]=a[1]+a[2]+…..+a[8]
lowbit(6)=2 c[6]=a[5]+a[6]

单点更新操作

图片.png
由上图可知，修改A[5]的值需要更新C[5],C[6],C[8]，因为C[5],C[6],C[8]覆盖了A[5]，C[5]好理解，毕竟更新了自己原数组上的值，但是要怎么知道更新的是C[6]，C[8]呢？
先上代码：

  1. void add(int i,int x) {
  2.     while(i <= n) {
  3.         c[i] += x;
  4.         i += lowbit(i);
  5.     }
  6. }

也就是说更新需要从i开始找一直到n，每次i更新为i+lowbit(i)
lowbit(i)是i二进制中最后一个1的位权，i+lowbit(i)表示在i的基础上至少扩大了两倍，也就是说C[i + lowbit(i)]会包含下标为i的原数组的值，因此也需要更新。

区间查询

图片.png
区间查询比较好理解，i每次需要往前走的步长是i-lowbit(i)，这个根据定义就可以得出.
比如前6项和，则C[6]需要往前找，C[6]表示前lowbit(6)=2项和，那么还需要加上i-lowbit(6)=6-2=4，由于4-lowbit(4)=0，因此S[6]=C[6] + C[4]，如果i - lowbit(i)还大于0，则需要继续寻找下一项C[i]。
上代码：

  1. int query(int i) {
  2.     int sum = 0;
  3.     while(i > 0) {
  4.         sum += c[i];
  5.         i -= lowbit(i);
  6.     }
  7.     return sum;
  8. }

根据前缀和数组恢复原数组：A[i]=query(i)-query(i-1).

树状数组完整代码：

  1. class FenwickTree {
  2.     int n;
  3.     int[] c;
  4.     int lowbit(int x) {
  5.         return x & (-x);
  6.     }
  7.     //初始化
  8.     FenwickTree(int n) {
  9.         this.n = n;
  10.         c = new int[n + 1];
  11.     }
  12.     //单点更新
  13.     void add(int i,int x) {
  14.         while(i <= n) {
  15.             c[i] += x;
  16.             i += lowbit(i);
  17.         }
  18.     }
  19.     //前缀和
  20.     int query(int i) {
  21.         int sum = 0;
  22.         while(i > 0) {
  23.             sum += c[i];
  24.             i -= lowbit(i);
  25.         }
  26.         return sum;
  27.     }
  28. }