树状数组

引入

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

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

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

需要注意的是：

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

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

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

树状数组

初步感受

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

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

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

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

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

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

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

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

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

例如，从图中可以看出：

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

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

举例：计算 的和。

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

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

举例：计算 的和。

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

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

管辖区间

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

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

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

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

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

因此， 代表 的区间信息。

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

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

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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8
9

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

区间查询

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

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6

def getsum(x): # a[1]..a[x]的和
    ans = 0
    while x > 0:
        ans = ans + c[x]
        x = x - lowbit(x)
    return ans

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

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

我们约定：

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

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

性质 ：在 真包含于 。

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

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

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

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

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

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

• 我们认为 的高度是 ，则点 的高度是 ，即 二进制最低位 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]，即 。

单点修改

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

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

管辖 的 一定包含 （根据性质 ），所以 在树状数组树形态上是 的祖先。因此我们从 开始跳父亲即可。

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

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

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

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

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

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

1
2
3
4
5
6

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

1
2
3
4

def add(x, k):
    while x <= n: # 不能越界
        c[x] = c[x] + k
        x = x + lowbit(x)

建树

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

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

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

也有 的建树方法，见本页面 建树 一节。

复杂度分析

空间复杂度显然 。

时间复杂度：

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

区间加区间和

前置知识：前缀和 & 差分。

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

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

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

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

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

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

因为差分是 ，

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

inline 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));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

t1 = [0] * MAXN, t2 = [0] * MAXN; n = 0

def lowbit(x):
    return x & (-x)

def add(k, v):
    v1 = k * v
    while k <= n:
        t1[k] = t1[k] + v; t2[k] = t2[k] + v1
        k = k + lowbit(k)

def getsum(t, k):
    ret = 0
    while k:
        ret = ret + t[k]
        k = k - lowbit(k)
    return ret

def add1(l, r, v):
    add(l, v)
    add(r + 1, -v)

def getsum1(l, r):
    return (r) * getsum(t1, r) - l * getsum(t1, l - 1) - \
          (getsum(t2, r) - getsum(t2, l - 1))

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

二维树状数组

单点修改，子矩阵查询

二维树状数组，也被称作树状数组套树状数组，用来维护二维数组上的单点修改和前缀信息问题。

与一维树状数组类似，我们用 表示 的矩阵总信息，即一个以 为右下角，高 ，宽 的矩阵的总信息。

对于单点修改，设：

即 为 在树状数组树形态上的第 级祖先（第 级祖先是自己）。

则只有 中的元素管辖 ，修改 时只需修改所有 ，其中 ，。