当前位置：首页 > news >正文

【数据结构】树状数组

news 来源：原创 2025/7/27 4:49:16

树状数组

假设一个数可以 $x$ 可以被二进制分解成 $x = 2^{i_1} + 2^{i_2} + ... + 2^{i_m}$ ，不妨设 $i_1 > i_2 > ... > i_m$ ，进一步地，区间 $[1, x]$ 可以分成 $O(log\ x)$ 个小区间：

长度为 $2^{i_1}$ 的小区间 $1, 2^{i_1}]$
长度为 $2^{i_2}$ 的小区间 $2^{i_1} + 1, 2^{i_1} + 2^{i_2}]$
$...$
长度为 $2^{i_m}$ 的小区间 $2^{i_1} + 2^{i_2} + ... + 2^{i_{m - 1}} + 1, 2^{i_1} + 2^{i_2} + ... + 2^{i_m}]$

这些小区间的共同特点是：若区间结尾为 $R$ ，则区间长度为 $l o w bi t (R)$ 。

树状数组，就是基于上述思想的数据结构，其基本用途是维护序列的前缀和。

对于给定的序列 $a$ ，建立数组 $c$ ，其中 $c [x]$ 的含义是以 $x$ 为结尾的，长度为 $l o w bi t (x)$ 的区间中所有数的和，即 $\sum_{i = x - lowbit(x) + 1}^{x} a[i]$ 。

单点更新：

void add(int x, int t) {for (int i = x; i <= n; i += lowbit(i)) c[i] += t;
}

区间查询：

int ask(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) res += c[i];
}

对于查询：

我们想要得知以区间 $[1, x]$ 的和，不妨从树状数组区间长度的划分和数组 $c$ 的定义出发。我们知道，对于长度为 $x$ 的区间，我们可以每次将其划分为长度为 $l o w bi t (x)$ 的区间，并 $x = x - l o w bi t (x)$ 。所以，我们很容易得到查询的代码。

复杂度是 $O(log\ n)$ 。

对于更新：

除树根外，每个内部节点 $c [x]$ 的父节点是 $c [x + l o w bi t (x)]$ 。

复杂度是 $\ n)$ 。

树状数组的扩展应用

以上介绍了树状数组的基本应用，即：

修改数组中的一个数。
查询区间和。

树状数组还有一些扩展应用，如：

扩展一：

将区间 $[l, r]$ 加上 $c$ 。
查询某个位置上的数。

扩展二：

将区间 $[l, r]$ 加上 $c$ 。
查询区间和。

扩展三： 结合其他算法(如：二分)实现更多功能

考虑扩展一

对于给定的序列 $a$ ，考虑其差分数组 $b$ 。

若想将区间 $[l, r]$ 加上一个数，可以对应在差分数组上执行 $b [l] = b [l] + c$ ， $b [r + 1] = b [r + 1] - c$ 。

若想查询某个位置 $x$ 的数，即求位置 $x$ 的前缀和。

以上两个操作是单点修改，区间查询。可以用树状数组解决。

考虑扩展二

对于区间给定的序列 $a$ ，考虑其差分数组 $b$ 。

若想将区间 $[l, r]$ 加上一个数，可以对应在差分数组上执行 $b [l] = b [l] + c$ ， $b [r + 1] = b [r + 1] - c$ 。

若想查询区间 $[1, r]$ 的和，即 $\sum_{i = 1}^r \sum_{j = 1}^{i}b_j$

对应代码为：

for (int i = 1; i <= r; i ++) for (int j = 1; j <= i; j ++) ans += b[j];

考虑以下表格

$a_1$	$b_1$
$a_2$	$b_1$	$b_2$
$a_3$	$b_1$	$b_2$	$b_3$
$...$
$a_i$	$b_1$	$b_2$	$...$	$b_m$

$a_1 = b_1$

$a_2 = b_1 + b_2$

$a_3 = b_1 + b_2 + b_3$

$...$

$a_i = b_1 + b_2 + ... + b_m$

则 $a_1 + a_2 + ... + a_i = (b_1 + b_2 + ... + b_m) \times (i + 1) - (b_1 + 2 \times b_2 + 3\times b_3 + ... + m\times b_m)$

可以看出，其转化成了 $b$ 数组的前缀和，以及 $i\times b[i]$ 数组的前缀和。可以用树状数组维护。

考虑扩展三

考虑如下问题，给定 $for\ (i = 1; i \leq n; i ++) \ cnt[i] = 1$ 表示 $1$ 到 $n$ 中所有数均可用。

现需要：每次找到所有可用数中第 $k$ 小的数，将该数存下，并将该数标记为不可用。

考虑维护数组 $c n t$ 的前缀和数组，标记为不可用只需将 $\leftarrow 0$ 。

前缀和每次可以算出有多少可用的数，然后可以二分。

所以该问题需要的操作是：单点修改和区间查询。配合二分可以实现更多功能。

树状数组

树状数组的扩展应用

考虑扩展一

考虑扩展二

考虑扩展三

相关文章：