树状数组

树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构，空间复杂度则为O(n)，通过将线性结构转化成树状结构，从而进行跳跃式扫描。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

A数组是原数组，c数组是树状数组，可以发现：

C1 = A1C2 = A1+A2C3 = A3C4 = A1+A2+A3+A4C5 = A5C6 = A5+A6C7 = A7

C8 = A1+A2+A3+A4+A5+A6+A7+A8

对任意n ,C[n]=A[n-2^k+1]+……A[n],k为n在二进制下末尾0的个数，例如n=6（110），k=1.

Lowbit：

用函数Lowbit（x）可以求出2^k:

int Lowbit(int x) { return x&(-x);    //或return x&(x^(x-1)); }

这里x&(-x)利用了机器补码的特性。

区间查询：

sum(a,b)=sum(1,b)-sum(1,a-1)任意求和均可转换为求sum(1,n)

n=7:

sum（1,7）=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ;   

C[4]=A[1]+A[2]+A[3]+A[4];   C[6]=A[5]+A[6];   C[7]=A[7];

可以推出:   sum[7]=C[7]+C[6]+C[4];

序号写为二进制: sum(1,(111))=C[(111)]+C[(110)]+C[(100)];

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

x-=Lowbit(x)实际上就是将x二进制最后一个1减去，得到上一个父节点。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。

单点更新：

要对最底层的值a[x]进行更新时，所有与它相关的父节点存储的和也需要进行更新。最坏情况下为修改第一个元素，最多有log(n)个祖先。

void update(int pos, int num) { while (pos <= N) //元素个数N { c[pos] += num; pos += Lowbit(x); } }

局限性：

不能进行区间更新；只能求和，不能求最值。

能用树状数组的都可以用线段树。