树状数组学习笔记

文章目录

原理代码实现（单点修改区间查询） 树状数组上二分代码实现卡常应用代码实现

原理

树状数组（binary index tree）可以以极小常数在 $\log$ 时间内维护前缀信息。

定义 $\mathrm{lowbit}(x)$ 表示 $x$ 的最低的二进制位， 如$\mathrm{lowbit}(2)=2,\mathrm{lowbit}(3)=1$， 则序列 $a$ 对应的树状数组 $b$ 维护的是 $[i-\mathrm{lowbit}(i)+1,i]$ 的区间信息。

由于 $i-\mathrm{lowbit}(i)$ 相当于是将 $i$ 的最低位删去， 故区间 $[1,i]$ 可以划分为 $\log n$ 个树状数组上的区间。 因此查询复杂度 $O(\log n)$。

另一方面，若 $x\in [i-\mathrm{lowbit}(i)+1,i]$，即 $i-\mathrm{lowbit}(i)<x\le i$，则显然 $i$ 除去最低位与 $x$ 相同，且 $x$ 要么最低位与 $i$ 的最低位相同，要么 $x$ 没有 $i$ 的最低位。因此，包含特定位置 $x$ 的区间个数不超过 $\log n$，修改操作为 $O(\log n)$。

代码实现（单点修改区间查询）

具体代码实现如下：（手玩一下其实正确性很显然的）

// a 为原序列， b 为树状数组 #define lowbit(x) ((x) & -(x)) inline void modify(int x, int k) { // a[x] += k for (; x <= n; x += lowbit(x)) b[x] += k; } inline int query(int x) { // a[1] + a[2] + ... + a[x] int k = 0; for (; x; x ^= lowbit(x)) k += b[x]; return k; }

树状数组上二分

比如，你开了一个序列的值域树状数组，打算用来求序列的第 $k$ 小。 设当前你枚举到区间 $(l,r]$，那么 每次选的区间中点是 $l+lim$，其中 $lim$ 表示小于 $r-l$ 的最大 $2$ 的整数次幂。数学归纳即可证明 $\mathrm{lowbit}(l+lim)=lim$。

代码实现

void init() { lim[2] = 1; for (int i = 3; i <= n; i++) lim[i] = lim[i - 1] << ((lim[i - 1] << 1) < i); } int find(int k) { int l = 0, r = n; while (l + 1 < r) { int mid = l + lim[r - l]; if (b[mid] < k) k -= b[mid], l = mid; else r = mid; } return l; }

卡常应用

比如，你要维护线段树支持的区间操作，同时还有在给定位置插入元素的操作，题目可以离线。

可以看出，解决问题的关键在于，把元素重新调整位置，使得插入的元素有位置可放。空的区间打上标记即可。

因此，考虑倒序处理，树状数组维护 $flag[i]$ 表示位置 $i$ 是否被占据。原先在第 $k$ 个位置后插入元素的操作，就相当于在倒序中的删除第 $k+1$ 个元素。这就成了单点修改、二分查找的问题。

代码实现

（上文中的预处理部分，这里原序列长 $n$， 有 $m$ 次操作）

int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { q[i].op = 1; q[i].x = i - 1; scanf("%d", &q[i].y); } m += n; for (int i = n + 1; i <= m; i++) scanf("%d %d %d", &q[i].op, &q[i].x, &q[i].y); // 没有封装的二分预处理 lim[2] = 1; for (int i = 3; i <= m; i++) lim[i] = lim[i - 1] << ((lim[i - 1] << 1) < i ? 1 : 0); for (int i = 1; i <= m; i++) modify(i, 1); for (int i = m; i >= 1; i--) { if (q[i].op == 2) { // 查询操作 q[i].x = search(q[i].x); q[i].y = search(q[i].y); } else { // 修改操作 q[i].x = search(q[i].x + 1); modify(q[i].x, -1); } }