树状数组
树状数组(Binary
Indexed Tree(BIT), Fenwick Tree)是一个查询和改动复杂度都为log(n)的数据结构。主要用于查询随意两位之间的全部元素之和，可是每次仅仅能改动一个元素的值；经过简单改动能够在log(n)的复杂度下进行范围改动，可是这时仅仅能查询当中一个元素的值。
基本概念：
如果数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，并且是一个在线的数据结构，支持随时改动某个元素的值，复杂度也为log级别。
来观察这个图：
树状数组的结构图
令这棵树的结点编号为C1，C2...Cn。令每一个结点的值为这棵树的值的总和，那么easy发现：
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
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
这里有一个有趣的性质：
我们来看一下这个规律，
C1(0001)末尾二进制0的个数是0，而且C1管辖的范围是C1=A1；
C2(0010)末尾二进制0的个数是1，而且C2管辖的范围是C2=A1+A2；
C3(0011)末尾二进制0的个数是0，而且C3管辖的范围是C3=A3；
......
C8(1000)末尾二进制0的个数是3，而且C2管辖的范围是C8=A1+A2+A3+A4+A5+A6+A7+A8；
设节点编号为x，那么这个节点管辖的区间为2^k（当中k为x二进制末尾0的个数）个元素。由于这个区间最后一个元素必定为Ax，
所以非常明显：Cn = A(n – 2^k + 1) + ... + An
基本操作：
1,对于C[i]=a[i - 2^k + 1]...a[i]的定义中，比較难以逐磨的k，他的值等于i这个数的二进制表示末尾0的个数.
如4的二进制表示0100,此时k就等于2，而实际上我们还会发现2^k就是前一位的权值,即0100中,2^2=4，刚好 是前一位数1的权值.所以所以2^k能够表示为n&(n^(n-1))或更简单的n&(-n)，比如：
为了表示简便，如果如今一个int型为4位,最高位为符号位
int i=3&(-3); 此时i=1，3的二进制为0011,-3的二进制为1101(负数存的是补码）所以0011&1101=1
int j=4&(-4); 此时j=4，理由同上.....
所以计算2^k我们能够用例如以下代码：
int lowbit(int n)
{
return n&(-n);
}
2,求和操作在上面的示意图中，若我们须要求sum[1..7]个元素的和，仅须要计算c[7]+c[6]+c[4]的和就可以，到底时间复杂度怎么算呢？一共要进行多少次求和操作呢？
n-=lowbit(n);这一项实际上等价于将当前二进制串中的最后一个1减去，由于数的二进制串中1的个数最多有log(n)个，所以它的时间复杂度为log(n);求sum[1..k],我们需查找k的二进制表示中1的个数次就能得到终于结果，所以时间复杂度为log(n)。
int GetSum(int n)
{
int sum=0;
while(n>0)
{
sum+=TreeArray[n];
n-=lowbit(n);
}
return sum;
}
以求sum[1..7]为例,二进制为0111,右边第一个1出如今第0位上,也就是说要从a[7]開始向前数1个元素(仅仅有a[7]),即c[7];
然后将这个1舍掉,得到6,二进制表示为0110,右边第一个1出如今第1位上,也就是说要从a[6]開始向前数2个元素(a[6],a[5]),即c[6];
然后舍掉用过的1,得到4,二进制表示为0100,右边第一个1出如今第2位上,也就是说要从a[4]開始向前数4个元素(a[4],a[3],a[2],a[1]),即c[4].
所以s[7]=c[7]+c[6]+c[4];
3,更新操作
在上面的示意图中，如果更改的元素是a[2],那么它影响到得c数组中的元素有c[2],c[4],c[8]，我们仅仅需一层一层往上改动就能够了,这个过程的最坏的复杂度也只是O(logN);
void update(int n,int num)
{
while(n<=MAX)
{
TreeArray[n]+=num;
n+=lowbit(n);
}
}
n+=lowbit(n);这一项实际上等价于在二进制串中补0；
以改动a[2]元素为例，须要改动c[2],2的二进制为0010,末尾补0为0100,即c[4]
4的二进制为0100，在末尾补0为1000即c[8]。所以我们须要改动的有c[2],c[4],c[8]