树状数组详解
树状数组
概念：
树状数据结构，通常维护一些带有差分性质的区间问题，比如单点加，单点乘，查询区间和，前后缀最大值、最小值等。
回顾线段树：
线段树得以快速修改和查询在于下传懒标记，而树状数组则是每次修改时，将标记上传，查询的时候不用像线段树一样每次 pushdown。区别之处在于标记传送的方式的不同。
树状数组的图示：
和线段树不同，我们定义一个点，其儿子的范围(就是存的哪一个区间的范围)是 [ i − 2 k + 1 , i ] [i-2^k+1,i] [i−2k+1,i] 其中 k k k 是 i i i 二进制下从后往前第一个为 1 1 1 的位置，下标从0开始计算，我们称这个值为 l o w b i t i lowbit_i lowbiti。
比如： l o w b i t 3 = l o w b i t ( 11 ) 2 = 2 0 = 1 lowbit_3=lowbit_{(11)_2}=2^0=1 lowbit3=lowbit(11)2=20=1。
先解决如何快速计算 l o w b i t lowbit lowbit 首先暴力枚举一个二进制位数，然后判断这一位在原数的二进制下是否是1，这样是 log n \log n logn 的，有点慢了。
考虑二进制的一些性质，因为二进制数也有着进位退位这个说法，假设一个数 x x x 它二进制下从后往前第一个 1 出现的位置为 k k k 那么如果将 x → x − 1 x→x-1 x→x−1 转换成二进制，就会变成 k k k 之前的还是那样， k k k 这个位置为 0 ， k k k 之后的位置都是 0。
比如 ( 10100 ) 2 − 1 10 → ( 10011 ) 2 (10100)_{2}-1_{10}→(10011)_2 (10100)2−110→(10011)2
这个时候我们再跟原数 x x x 进行异或操作，就变成了 10100 x o r 10010 10100 xor 10010 10100xor10010 就变成了 00111 00111 00111 然后再跟原数 x x x 取 & 操作，也就是把 k k k 之后那些没用的 0 给挤掉。
int lowbit(int x){return x&(x^(x-1));
}
这样有点复杂啊，怎么让他好看点呢？
由于补码是反码+1，也就是 10100 10100 10100
反码： 01011 01011 01011
补码： 01100 01100 01100
好玩的事情出现了，我们发现补码的+1会一直进位，什么时候不进位呢，显然就是进位到一个位置 k k k 这个地方为0，就会停止进位，而这个0正是原数反码中的从后往前的第一个出现的1的位置，这样把两个数 & 起来结果就对了。
那么知道了这些，树状数组有哪些性质呢？
- 对于节点 i i i 其直接父亲编号为 i + l o w b i t i i+lowbit_i i+lowbiti
那么修改的时候我们就可以把所有的 x > i x>i x>i 满足 x x x 中有 i i i 的信息都给打上标记。
单点修改打标记的时间复杂度：
由于我们发现 x → x + l o w b i t x x→x+lowbit_x x→x+lowbitx 的操作实际上是进位操作，所以最多会进行 log 2 V \log_2 V log2V 次操作， V V V 是树状数组节点个数，也就是树状数组值域。
这样修改操作就可以了，我们看查询操作：
前文已经提及了，树状数组需要满足差分性质，比如求区间和就有差分性质，求区间 ∑ i = l r a i \sum_{i=l}^r a_i ∑i=lrai 的值，就可以求 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i \sum_{i=1}^ra_i-\sum_{i=1}^{l-1}a_i ∑i=1rai−∑i=1l−1ai