树状数组

jesse1216 · 2023-06-10 09:04:44 · 算法·理论

前置知识

求二进制中 x 的最低位，\text{lowbit}(x)=x\ \&\ (-x)。

算法介绍

单点修改，区间查询：给定一个 n 项的数列 a，你需要实现两种操作：(1) 将 a_x 加上 y；(2) 求出 a_x+a_{x+1}+\dots+a_y 的值。数据范围 1\le n,m\le10^6。

1. 前缀和

令 s_i=a_1+a_2+\dots+a_i，于是 a_x+a_{x+1}+\dots+a_y=s_y-s_{x-1}，可以 O(1) 得出。但修改时需要把 s_x,s_{x+1},\dots,s_n 全部加 y，复杂度为 O(n)。

在最差情况下，修改次数很多，这时复杂度为 O(nm)，无法通过。

2. 分块（优化的前缀和）

把数列分为 k 段，每一段 \frac{n}{k} 个数，对每一段分别统计前缀和。

在每次查询时，中间的整块（最多有 k 块）可以直接加上，两侧的块也可以前缀和相减得到，所以复杂度为 O(k)。

在每次修改时，只需要把 x 所在的块的前缀和数组修改，复杂度 O(\frac{n}{k})。

所以总复杂度最高为 O(m\cdot\max(k,\frac{n}{k}))。显然 k=\frac{n}{k}，即 k=\sqrt{n} 时最小，复杂度 O(m\sqrt{n})。

这个算法可以通过大部分数据，但 n=m=10^6 时，m\sqrt{n}=10^9，无法通过。

3. 树状数组

用二进制优化前缀和：

我们把 s_i 按照 i 的二进制分成了若干个部分，例如 5=(101)_2，所以把 s_5 分为了 4 个数加上 1 个数。

构造 t 数列：

仔细观察上面的图，可以发现如下规律：

• 求 s_x：

从 x 开始，每次加上 t_x，再将 x 减去最低位，直到 x=0。

以 x=7 为例，7=(111)_2，(111)_2\rightarrow(110)_2\rightarrow(100)_2\rightarrow(000)_2，所以 s_7=t_7+t_6+t_4。

• 将 a_x 增加 k：

从 x 开始，每一次将 t_x 加 k，再将 x 加上最低位，直到 x>n。

以 x=3 为例，3=(0011)_2，(0011)_2\rightarrow(0100)_2\rightarrow(1000)_2，所以将 a_3、a_4、a_8 加上 k 即可。

这两个操作的复杂度均为 O(\log n)，因为每操作一次都能“搞定” x 的一位。

代码