树状数组

lowbit()

lowbit(x)是x的二进制表达式中最低位的1所对应的值（即返回x二进制为一的最低位数值）。

lowbit(0)=0

常用写法：

int lowbit(int x){
	return x&(-x);
}
//利用了负整数的补码特性

用法

维护区间

设节点编号为x，那么该节点维护的区间和是 $ ( x – lowbit ( x ) , x ] $ 。

树状数组

基本操作复杂度： $ O ( logn ) $

树状数组利用了lowbit()来进行区间维护。

令父节点储存其子节点之和，

则不难发现：

$ C [ i ] = A [ i – 2k + 1 ] + A [ i – 2k + 2 ] + …… A [ i ] $

（k为i的二进制中从最低位到高位连续零的长度）

lowbit(x) 就是取出x的最低位1,换言之lowbit(x)=2k, k的含义与上面相同,所以：

$ C [ i ] = A [ i – lowbit ( i ) + 1 ] + A [ i – lowbit ( i ) + 2 ] + …… A [ i ] $

主要性质

性质1

每个内部结点 $ C [ x ] $ 保存以它为根的子树中所有叶结点的和。

应用

前缀和查询

区间和查询

$ sum ( y ) – sum ( x – 1 ) $

性质2

每个内部结点 $ C [ x ] $ 的子结点个数等于其lowbit(x)的值。

性质3

除树根以外，每个内部结点 $ C [ x ] $ 的父亲结点是 $ C [ x + lowbit ( x ) ] $

应用

单点修改

性质4

树的深度为 $ O ( logn ) $ 。

注意

树状数组只能处理下标为1…n的数组，绝不能出现下标为0的情况。因为lowbit(0)=0，会陷入死循环。

拓展

一维树状数组的每个操作都是 $ O ( logn ) $ ，它可扩展到m维,复杂度变成 $ O ( log^m n ) $

扩展方法

将原来的修改和查询函数中的一个循环，改成m个循环（m维数组c中的操作），以二维为例：

并非原创，仅是整理，请见谅