数据结构：树状数组

Posted on 2024-04-17 Edited on 2024-09-07 In 数据结构 Views:

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。

什么是「单点修改」和「区间查询」？

假设有这样一道题：

已知一个数列，你需要进行下面两种操作：

给定，将自增。

给定，求解的和。

其中第一种操作就是「单点修改」，第二种操作就是「区间查询」。

类似地，还有：「区间修改」、「单点查询」。它们分别的一个例子如下：

区间修改：给定，将中的每个数都分别自增；

单点查询：给定，求解的值。

注意到，区间问题一般严格强于单点问题，因为对单点的操作相当于对一个长度为的区间操作。

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。

结合律：，其中是一个二元运算符。
可差分：具有逆运算的运算，即已知和可以求出。

需要注意的是：

模意义下的乘法若要可差分，需保证每个数都存在逆元（模数为质数时一定存在）；
例如，这些信息不可差分，所以不能用普通树状数组处理，但是：
- 使用两个树状数组可以用于处理区间最值，见 Efficient Range Minimum Queries using Binary Indexed Trees。
- 本页面也会介绍一种支持不可差分信息查询的，时间复杂度的拓展树状数组。

事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。

树状数组

初步感受

先来举个例子：我们想知道的前缀和，怎么做？

一种做法是：，需要求个数的和。

但是如果已知三个数，，，的和，的总和，的总和（其实就是自己）。你会怎么算？你一定会回答：，只需要求个数的和。

这就是树状数组能快速求解信息的原因：我们总能将一段前缀拆成 不多于段区间，使得这段区间的信息是 已知的。

于是，我们只需合并这段区间的信息，就可以得到答案。相比于原来直接合并个信息，效率有了很大的提高。

不难发现信息必须满足结合律，否则就不能像上面这样合并了。

下面这张图展示了树状数组的工作原理：

最下面的八个方块代表原始数据数组。上面参差不齐的方块（与最上面的八个方块是同一个数组）代表数组的上级—— 数组。

数组就是用来储存原始数组某段区间的和的，也就是说，这些区间的信息是已知的，我们的目标就是把查询前缀拆成这些小区间。

例如，从图中可以看出：

管辖的是；
管辖的是；
管辖的是；
管辖的是；
剩下的管辖的都是自己（可以看做的长度为的小区间）。

不难发现，管辖的一定是一段右边界是的区间总信息。我们先不关心左边界，先来感受一下树状数组是如何查询的。

举例：计算的和。

过程：从开始往前跳，发现只管辖这个元素；然后找，发现管辖的是，然后跳到，发现管辖的是这些元素，然后再试图跳到，但事实上不存在，不跳了。

我们刚刚找到的是，事实上这就是拆分出的三个小区间，合并得到答案是。

举例：计算的和。

我们还是从开始跳，跳到再跳到。此时我们发现它管理了的和，但是我们不想要这一部分，怎么办呢？很简单，减去的和就行了。

那不妨考虑最开始，就将查询的和转化为查询的和，以及查询的和，最终将两个结果作差。

管辖区间

那么问题来了，管辖的区间到底往左延伸多少？也就是说，区间长度是多少？

树状数组中，规定管辖的区间长度为，其中：

设二进制最低位为第位，则恰好为二进制表示中，最低位的 1 所在的二进制位数；
（的管辖区间长度）恰好为二进制表示中，最低位的 1 以及后面所有 0 组成的数。

举个例子，管辖的是哪个区间？

因为，其二进制最低位的 1 以及后面的 0 组成的二进制是 1000，即，所以管辖个数组中的元素。

因此，代表的区间信息。

我们记二进制最低位 1 以及后面的 0 组成的数为，那么管辖的区间就是。

这里注意：指的不是最低位 1 所在的位数，而是这个 1 和后面所有 0 组成的。

怎么计算 lowbit？根据位运算知识，可以得到 lowbit(x) = x & -x。

lowbit 的原理

将 x 的二进制所有位全部取反，再加 1，就可以得到 -x 的二进制编码。例如，的二进制编码是 110，全部取反后得到 001，加 1 得到 010。

设原先 x 的二进制编码是 (...)10...00，全部取反后得到 [...]01...11，加 1 后得到 [...]10...00，也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1 是 x 最低位的 1。

(...) 和 [...] 中省略号的每一位分别相反，所以 x & -x = (...)10...00 & [...]10...00 = 10...00，得到的结果就是 lowbit。

int lowbit(int x) {
  // x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;
}

区间查询

接下来我们来看树状数组具体的操作实现，先来看区间查询。

回顾查询的过程，我们是将它转化为两个子过程：查询和查询的和，最终作差。

其实任何一个区间查询都可以这么做：查询的和，就是的和减去的和，从而把区间问题转化为前缀问题，更方便处理。

事实上，将有关的区间询问转化为和的前缀询问再差分，在竞赛中是一个非常常用的技巧。

那前缀查询怎么做呢？回顾下查询的过程：

从往前跳，发现只管辖这个元素；然后找，发现管辖的是，然后跳到，发现管辖的是这些元素，然后再试图跳到，但事实上不存在，不跳了。

我们刚刚找到的是，事实上这就是拆分出的三个小区间，合并一下，答案是。

观察上面的过程，每次往前跳，一定是跳到现区间的左端点的左一位，作为新区间的右端点，这样才能将前缀不重不漏地拆分。比如现在管的是，下一次就跳到，即访问。

我们可以写出查询的过程：

从开始往前跳，有管辖；
令，如果说明已经跳到尽头了，终止循环；否则回到第一步。
将跳到的合并。

实现时，我们不一定要先把都跳出来然后一起合并，可以边跳边合并。

比如我们要维护的信息是和，直接令初始，然后每跳到一个就，最终就是所有合并的结果。

int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x > 0) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

树状数组与其树形态的性质

在讲解单点修改之前，先讲解树状数组的一些基本性质，以及其树形态来源，这有助于更好理解树状数组的单点修改。

我们约定：

。即，是管辖范围的左端点。
对于任意正整数，总能将表示成的形式，其中。
下面「和不交」指的管辖范围和的管辖范围不相交，即和不相交。「包含于」等表述同理。

性质：对于，要么有和不交，要么有包含于。

Proof：

假设和相交，即和相交，则一定有。

将表示为，则。所以，可以表示为，其中。

不难发现。又因为，

所以，即。

所以，如果和相交，那么的管辖范围一定完全包含于。

性质：在真包含于。

Proof：

设，，则，。

不难发现，所以，即。

所以，真包含于。

性质：对于任意，有和不交。

Proof：

设，则，其中。

不难发现。又因为，

因此，即。

所以，和不交。

有了这三条性质的铺垫，我们接下来看树状数组的树形态（请忽略向的连边）。

事实上，树状数组的树形态是向连边得到的图，其中是的父亲。

注意，在考虑树状数组的树形态时，我们不考虑树状数组大小的影响，即我们认为这是一棵无限大的树，方便分析。实际实现时，我们只需用到的，其中是原数组长度。

这棵树天然满足了很多美好性质，下面列举若干（设表示的直系父亲）：

。
大于任何一个的后代，小于任何一个的祖先。
点的严格小于的。

证明：设，，则，不难发现，证毕。

点的高度是，即二进制最低位 1 的位数。

高度的定义：

点的高度满足：如果，则，否则，其中代表的所有儿子（此时至少存在一个儿子）。

也就是说，一个点的高度恰好比它最高的那个儿子再高。如果一个点没有儿子，它的高度是。

这里引出高度这一概念，是为后面解释复杂度更方便。

真包含于（性质）。
真包含于，其中是的任一祖先（在上一条性质上归纳）。
真包含，其中是的任一后代（上面那条性质，颠倒）。
对于任意，若不是的祖先，则和不交。

证明：和的祖先中，一定存在一个点使得，根据性质得不相交于，而包含，因此不交于。

对于任意，如果不在的子树上，则和不交（上面那条性质，颠倒）。
对于任意，当且仅当是的祖先，真包含于（上面几条性质的总结）。这就是树状数组单点修改的核心原理。
设，则其儿子数量为，编号分别为。
- 举例：假设，的二进制编号为 ...1000，则有三个儿子，二进制编号分别为 ...0111、...0110、...0100。

证明：

在一个数的基础上减去，二进制第位会反转，而更低的位保持不变。

考虑的儿子，有，即且。设。

考虑，的第位及后方均为，所以的第位变为，后面仍为，满足。

考虑，则，的第位变为，不满足 。

考虑，则，的第位是，所以，不满足 。

的所有儿子对应的管辖区间恰好拼接成。

举例：假设，的二进制编号为 ...1000，则有三个儿子，二进制编号分别为 ...0111、...0110、...0100。
c[...0100] 表示 a[...0001 ~ ...0100]。
c[...0110] 表示 a[...0101 ~ ...0110]。
c[...0111] 表示 a[...0111 ~ ...0111]。
不难发现上面是三个管辖区间的并集恰好是 a[...0001 ~ ...0111]，即。

证明：

的儿子总能表示成，不难发现，越小，越大，代表的区间越靠右。我们设，则分别构成从左到右的儿子。

不难发现，所以。

考虑相邻的两个儿子和。前者管辖区间的右端点是，后者管辖区间的左端点是，恰好相接。

考虑最左面的儿子，其管辖左边界恰为。

考虑最右面的儿子，其管辖右边界就是。

因此，这些儿子的管辖区间可以恰好拼成。

单点修改

现在来考虑如何单点修改。

我们的目标是快速正确地维护数组。为保证效率，我们只需遍历并修改管辖了的所有，因为其他的显然没有发生变化。

管辖的一定包含（根据性质），所以在树状数组树形态上是的祖先。因此我们从开始不断跳父亲，直到跳得超过了原数组长度为止。

设表示的大小，不难写出单点修改的过程：

初始令。
修改。
令，如果说明已经跳到尽头了，终止循环；否则回到第二步。

区间信息和单点修改的种类，共同决定的修改方式。下面给几个例子：

若维护区间和，修改种类是将加上，则修改方式则是将所有也加上。
若维护区间积，修改种类是将乘上，则修改方式则是将所有也乘上。

然而，单点修改的自由性使得修改的种类和维护的信息不一定是同种运算，比如，若维护区间和，修改种类是将赋值为，可以考虑转化为将加上。如果是将乘上，就考虑转化为加上。

下面以维护区间和，单点加为例给出实现。

void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

建树

也就是根据最开始给出的序列，将树状数组建出来（全部预处理好）。

一般可以直接转化为次单点修改，时间复杂度（复杂度分析在后面）。

比如给定序列要求建树，直接看作对单点加，对单点加，对单点加即可。

也有的建树方法，见本博客后文建树一节。

复杂度分析

空间复杂度显然。

时间复杂度：

对于区间查询操作：整个的迭代过程，可看做将二进制中的所有，从低位到高位逐渐改成的过程，拆分出的区间数等于二进制中的数量（即）。因此，单次查询时间复杂度是；
对于单点修改操作：跳父亲时，访问到的高度一直严格增加，且始终有。由于点的高度是，所以跳到的高度不会超过，所以访问到的的数量是级别。因此，单次单点修改复杂度是。

区间加区间和

本小节需要了解前缀和和差分的部分知识。

该问题可以使用两个树状数组维护差分数组解决。

考虑序列的差分数组，其中。由于差分数组的前缀和就是原数组，所以。

一样地，我们考虑将查询区间和通过差分转化为查询前缀和。那么考虑查询的和，即，进行推导：

观察这个式子，不难发现每个总共被加了次。接着推导：

并不能推出的值，所以要用两个树状数组分别维护和的和信息。

那么怎么做区间加呢？考虑给原数组区间加给带来的影响。

因为差分是，

多了而不变，所以的值多了。
不变而多了，所以的值少了。
对于不等于且不等于的任意，和要么都没发生变化，要么都加了，还是，所以其它的均不变。

那就不难想到维护方式了：对于维护的树状数组，对单点加，单点加；对于维护的树状数组，对单点加，单点加。

而更弱的问题，「区间加求单点值」，只需用树状数组维护一个差分数组。询问的单点值，直接求的和即可。

这里直接给出「区间加区间和」的代码：

int t1[MAXN], t2[MAXN], n;

int lowbit(int x) { return x & (-x); }

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    // 注意不能写成 t2[k] += k * v，因为 k 的值已经不是原数组的下标了
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}

根据这个原理，应该可以实现「区间乘区间积」，「区间异或一个数，求区间异或值」等，只要满足维护的信息和区间操作是同种运算即可，感兴趣的读者可以自己尝试。

//待续