【复健】树状数组2

树状数组复健2

注：因为习惯和省事问题，下文的 \(lowbit\) 代表 \(lowerbit\),但后者也会时而出现。

为什么重写

↑您不觉得我这玩意写得逻辑不通吗而且抽象

关于树状数组

是什么

并不是一种树形结构。

↑按照我的理解这玩意差不多长成这个样，类似砖头

通过一些分散的小区间来储存数据，每个数据可能会同时出现在多个区间内。包含同一个数据的相邻两个区间之间间隔 \(lowerbit(x)\),即截留下这个数的最末位 \(1\)及其之后的 \(0\) 所形成的数。

为什么

快（这不废话吗

对于一个普通数组，单点修改的复杂度是 \(O(1)\),区间查询的复杂度是 \(O(n)\);对于一个前缀和数组，区间查询的复杂度是 \(O(1)\),但单点修改的复杂度是 \(O(n)\).

其中 \(n\) 为区间长度。

树状数组单点修改和区间查询的复杂度都是 \(O(\log n)\).

另外一点是，如果实在没时间打线段树，树状数组的码量会小一点。

关于 lowbit 运算

\(e.g.\)

\(x = (11001)_2\) 是一个二进制奇数，我们知道 \(-x = (10011001)_2\), 即把符号位变成 \(1\)。

\(x\) 的补码是原码，\(-x\) 的补码就是它的反码 \(+1\), 而：

所以可得 \(x\) 的补码为 \((11010)_2\), \(-x\) 的补码为 \((11100111)_2\), \(x \& (-x) = (1)_2\), 就取到了 \(x\) 的最后一位 \(1\).

因为正数的补码和原码相同，负数的补码和对应的正数相比，除了最后一位 \(1\) 及其以后的 \(0\), 其它的全部取反，按位与结果为 \(0\). 这样就获取到末位 \(1\) 了。

偶数比如 \(10000\) 和 \(10010000\), 显然后者在取反后会变为 \(11101111\), 实际上是与 \(10000\) 完全相反（包括符号位）的，所以 \(+1\) 后我们就会看到 \(-x\) 的补码为 \(11110000\),从而得到 \(10000\) 最末位的 \(1\).

代码实现

因为是砖头（？）式排列 法，可以参考在砖墙上涂鸦（？

修改一种砖头的纹路需要把所有包含这种纹路的砖头都修改，查询类比前缀和。

其实不看成砖头理解起来也没有任何麻烦（

注：默认原始数组为 \(a\),树状数组为 \(bit\),数组大小为 \(n\).

单点修改

因为区间间隔是 \(lowbit(x)\),所以循环的步长就是这么多。

void update1(int i, int x) {
	for(int pos = i; pos <= n; pos += lowbit(pos)) bit[i] += x;
}

区间修改

只需要把单点修改丢进 \(for\) 循环即可：

void update2(int l, int r, int x) {
	for(int i = l; i <= r; ++i) update1(i, x);
}

求前 n 项和

第一个区间不一定包含第 \(n\) 项，对其执行 \(lowbit\) 操作所得到的区间也不一定包含。

但是反过来，先查询第 \(n\) 个区间是可以的。第 \(n\) 个区间一定包含第 \(n\) 项。

为什么？

再看看这行代码：for(int pos = i; pos <= n; pos += lowbit(pos)),在初始化时我们必然使用 update1 操作来初始化每个编号为 \(i\) 的点，而这个操作是从第 \(i\) 个区间开始的。

int query1(int i) {
	int ans = 0;
	for(int pos = i; pos; pos -= lowbit(x)) ans += bit[pos];
	return ans;
}

区间查询

类比前缀和。

int query2(int l, int r) {
	return query1(r) - query1(l - 1); 
}

如果想要单点查询， 直接 query(i, i) 即可。

例题们

咕咕咕