树状数组 BIT 总结
树状数组 BIT 总结
0x00 功能
树状数组，即BIT，用于在
- 结合律：
\oplus 表示一种运算，若对于任意x,y,z ，有\left(x\oplus y\right)\oplus z=x\oplus \left(y\oplus z\right) 。
0x01 实现
下面讲解都以前缀和为例
定义
使用树状结构对每一个区间使用二进制进行划分，如下图：
对于节点
其中
-
表示 $x$ 二进制最低位 `1` 以及后面的 `0` 组成的数。如 $lowbit\left(10010100_{\left(2\right)}\right)=100_{\left(2\right)} -
arr 表示需处理的数组。
-
size 表示需处理的数组大小。
推论
-
对于节点
i,1\leq i\lt 2^{n} 其祖先必有2^n 这个节点证明：我们对于
i 不考虑第二进制下第n 位的数，即考虑i\&\left(2^{n}-1\right) ，设其为x 假设其可以经过2^{n-1} 这个节点。这时考虑第n 位的数，若为0 则加上\operatorname{lowbit}\left(2^{n-1}\right)=2^{n-1} 则到了2^n 的节点；若为1 直接进位到2^n 。那么对于边界情况当i=1 时显然有此结论。数学归纳法 Q.E.D. -
对于节点
i 可以管辖的范围为\left[i-\operatorname{lowbit}\left(i\right)+1,i\right] ，其值为这个区间的arr 值之和。证明：对于
x\in\left[i-\operatorname{lowbit}\left(i\right)+1,i\right] 这个节点先不考虑\operatorname{lowbit}\left(i\right) 这一位和前面的所有数，即考虑x\&\left(\operatorname{lowbit}\left(i\right)-1\right) 。由于上一条推论以可以知道x 可以走到\operatorname{lowbit}\left(i\right) 这个节点，这时加上前面的数就是i 这个节点，证得对于x\in\left[i-\operatorname{lowbit}\left(i\right)+1,i\right] 这个节点祖先必有。而这样推之所以正确是因为\operatorname{lowbit}\left(x\right) 只关注最后一个1 前面的数并无影响。Q.E.D.
-
对于节点
i 不能管辖\left[i-\operatorname{lowbit}\left(i\right)+1,i\right] 以外的范围，其值为这个区间的arr 值之和。当
x=i-\operatorname{lowbit}\left(x\right) 时，由于上一条推论可知其管辖范围为\left[x-\operatorname{lowbit}\left(x\right)+1,x\right] 而x+\operatorname{lowbit}\left(x\right) \gt i ，因为i-\operatorname{lowbit}\left(i\right) 实际上就是把i 最后一个1 去掉，那么\operatorname{lowbit}\left(i-\operatorname{lowbit}\left(i\right)\right) 就是剩下部分的最后一个1 ，即i 的倒数第二个1 显然更大。当
x=i-\operatorname{lowbit}\left(i-\operatorname{lowbit}\left(i\right)\right) 时，也有x+\operatorname{lowbit}\left(x\right) \gt i 相当于这时减了最后两个1 ，此时\operatorname{lowbit}\left(x\right) 就是倒数第三个1 ，显然大于倒数两个的1 的和，因为位数都不同。进而继续递归这个过程即可。
当
x\gt i 显然不会有父亲小于i ，因为\operatorname{lowbit} 永远大于0 。Q.E.D.
求解
查询
假设现在我们需要求前缀和到
修改
同理一直加上
0x02 Tricks
单点修改 区间查询
刚才实现的都是 单点修改 前缀查询 ，若这个运算具有差分性质，就可以实现 单点修改 区间查询 。
- 差分性质：
\oplus 表示一种运算，若对于任意x,y 。已知x\oplus y 和 其中一者可求得另一者。
直接维护差分数组即可。
\mathcal{O}\left(n\right) 建树
建树朴素方法就是每个点加上