树状数组入门

树状数组又叫二叉索引树，它是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改and区间求和。另外一个拥有类似功能的是线段树。

具体区别和联系如下：

1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.

2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.

3.树状数组的突出特点是其编程的极端简洁性, 使用lowbit函数可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。

上面出现了一个新名词:lowbit.其实lowbit(x)就是求x最低位的1;

树状数组的画法：

$C[i]$代表 子树的叶子结点的权值之和

如图可以知道

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

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

再将其转化为二进制看一下:

    C[1] = C[0001] = A[1];

    C[2] = C[0010] = A[1]+A[2];

    C[3] = C[0011] = A[3];

    C[4] = C[0100] = A[1]+A[2]+A[3]+A[4];

    C[5] = C[0101] = A[5];

    C[6] = C[0110] = A[5]+A[6];

    C[7] = C[0111] = A[7];

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

对照式子可以发现$C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i];​$ （k为i的二进制中从最低位到高位连续零的长度）

例如$i=8(1000)​$时，$k=3​$;$C[8] = A[8-2^3+1]+A[8-2^3+2]+......+A[8]​$

其实不难看出lowbit(i)便是上面的2^k，因为$2^k$后面一定有$k$个$0$比如说$2^5==>100000$，正好是$i$最低位的$1$加上后缀$0$所得的值。

---

lowbit函数实现

代码实现：

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

如：

0110(2)=6，变为反码后为 0001，再加1为 0010 即它的补码。

可以发现变为反码后 x 与反码数字位每一位都不同， 所以当反码加1后神奇的事情发生了，反码会逢1一直进位直到遇到0，且这个0变成了1，所以这个数最后面出现了一个 100… 串。 由于是反码，进位之后由于1的作用使进位的部分全部取反及与原码相同，所以可以发现 lowbit 以前的部分 x 与其补码即 -x 相反， lowbit x 与 -x 都是1，lowbit 以后 x 与 -x 都是0 所以 x&-x 后除了 lowbit 位是1，其余位都是0

---

单点更新

此时如果我们要更改A[1]

则有以下需要进行同步更新:

1(001) C[1]+=A[1]

lowbit(1)=001 1+lowbit(1)=2(010) C[2]+=A[1]

lowbit(2)=010 2+lowbit(2)=4(100) C[4]+=A[1]

lowbit(4)=100 4+lowbit(4)=8(1000) C[8]+=A[1]

代码实现:

void update(int x, int y, int n) {   //x为更新的位置,y为更新后的数,n为数组最大值
    for(int i = x; i <= n; i+= lowbit(i))
        c[i] += y;
}

---

区间查询

如：i=5时

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

可以推出: sum(i = 5) ==> C[4]+C[5];

序号写为二进制:$sum(101)=C[(100)]+C[(101)]$;

第一次$101$,减去最低位的$1$就是$100$;

其实也就是单点更新的逆操作。

int getsum(int x) {
    int ans = 0;
    for(int i = x; i; i -= lowbit(i))
        ans += c[i];
   	return ans;
}