数据结构：树状数组续

Posted on Edited on In Views:

由于树状数组内容较多，因此分为两篇博客介绍。

本篇博客在上一篇的基础上，介绍二维树状数组、权值树状数组等数据结构以及树状数组的维护和技巧。

二维树状数组

单点修改，子矩阵查询

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

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

对于单点修改，设：

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

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

正确性证明：

管辖 ，求 和 的取值范围。

考虑一个大小为 的一维树状数组 （对应原数组 ）和一个大小为 的一维树状数组 （对应原数组 ）。

则命题等价为： 管辖 且 管辖 的条件。

也就是说，在树状数组树形态上， 是 及其祖先中的一个点， 是 及其祖先中的一个点。

所以 ，。

对于查询，我们设：

则合并所有 ，其中 。

正确性证明：

设 表示合并两个信息的运算符（比如，如果信息是区间和，则 ）。

考虑一个一维树状数组 ， 恰好表示原数组上 这段区间信息。

类似地，设 ，则 恰好表示 这个矩阵信息。

又类似地，就有 表示 这个矩阵信息。

其实这里 这个函数如果看成一个树状数组，相当于一个树状数组套了一个树状数组，这也就是「树状数组套树状数组」这个名字的来源。

下面给出单点加、查询子矩阵和的代码。

1
2
3
4
5
6
7
8
9
//单点加
void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      // 注意这里必须得建循环变量，不能像一维数组一样直接 while (x <= n) 了
      c[i][j] += v;
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//查询子矩阵和
int sum(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      res += c[i][j];
    }
  }
  return res;
}

int ask(int x1, int y1, int x2, int y2) {
  // 查询子矩阵和
  return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 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
26
27
28
29
30
31
32
33
typedef long long ll;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];

void add(ll x, ll y, ll z) {
  for (int X = x; X <= n; X += lowbit(X))
    for (int Y = y; Y <= m; Y += lowbit(Y)) {
      t1[X][Y] += z;
      t2[X][Y] += z * x;  // 注意是 z * x 而不是 z * X，后面同理
      t3[X][Y] += z * y;
      t4[X][Y] += z * x * y;
    }
}

void range_add(ll xa, ll ya, ll xb, ll yb,
               ll z) {  //(xa, ya) 到 (xb, yb) 子矩阵
  add(xa, ya, z);
  add(xa, yb + 1, -z);
  add(xb + 1, ya, -z);
  add(xb + 1, yb + 1, z);
}

ll ask(ll x, ll y) {
  ll res = 0;
  for (int i = x; i; i -= lowbit(i))
    for (int j = y; j; j -= lowbit(j))
      res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] -
             (x + 1) * t3[i][j] + t4[i][j];
  return res;
}

ll range_ask(ll xa, ll ya, ll xb, ll yb) {
  return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}

权值树状数组及应用

我们知道，普通树状数组直接在原序列的基础上构建， 表示的就是 的区间信息。

然而事实上，我们还可以在原序列的权值数组上构建树状数组，这就是权值树状数组。

什么是权值数组？

一个序列 的权值数组 ，满足 的值为 在 中的出现次数。

例如： 的权值数组为 。

很明显， 的大小和 的值域有关。

若原数列值域过大，且重要的不是具体值而是值与值之间的相对大小关系，常 离散化 原数组后再建立权值数组。

另外，权值数组是原数组无序性的一种表示：它重点描述数组的元素内容，忽略了数组的顺序，若两数组只是顺序不同，所含内容一致，则它们的权值数组相同。

因此，对于给定数组的顺序不影响答案的问题，在权值数组的基础上思考一般更直观，比如 [NOIP2021] 数列。

运用权值树状数组，我们可以解决一些经典问题。

单点修改，查询全局第 小

在此处只讨论第 小，第 大问题可以通过简单计算转化为第 小问题。

该问题可离散化，如果原序列 值域过大，离散化后再建立权值数组 。注意，还要把单点修改中的涉及到的值也一起离散化，不能只离散化原数组 中的元素。

对于单点修改，只需将对原数列的单点修改转化为对权值数组的单点修改即可。具体来说，原数组 从 修改为 ，转化为对权值数组 的单点修改就是 单点减 ， 单点加 。

对于查询第 小，考虑二分 ，查询权值数组中 的前缀和，找到 使得 的前缀和 而 的前缀和 ，则第 大的数是 （注：这里认为 的前缀和是 ）。

这样做时间复杂度是 的。

考虑用倍增替代二分。

设 ，，枚举 从 降为 ：

  • 查询权值数组中 的区间和 。
  • 如果 ，扩展成功，，；否则扩展失败，不操作。

这样得到的 是满足 前缀和 的最大值，所以最终 就是答案。

看起来这种方法时间效率没有任何改善，但事实上，查询 的区间和只需访问 的值即可。

原因很简单，考虑 ，它一定是 ，因为 之前只累加过 满足 。因此 表示的区间就是 。

如此一来，时间复杂度降低为 。

1
2
3
4
5
6
7
8
9
10
11
12
// 权值树状数组查询第 k 小
int kth(int k) {
  int sum = 0, x = 0;
  for (int i = log2(n); ~i; --i) {
    x += 1 << i;                    // 尝试扩展
    if (x >= n || sum + t[x] >= k)  // 如果扩展失败
      x -= 1 << i;
    else
      sum += t[x];
  }
  return x + 1;
}

全局逆序对（全局二维偏序）

全局逆序对也可以用权值树状数组巧妙解决。问题是这样的：给定长度为 的序列 ，求 中满足 且 的数对 的数量。

该问题可离散化，如果原序列 值域过大，离散化后再建立权值数组 。

我们考虑从 到 倒序枚举 ，作为逆序对中第一个元素的索引，然后计算有多少个 满足 ，最后累计答案即可。

事实上，我们只需要这样做（设当前 ）：

  • 查询 的前缀和，即为左端点为 的逆序对数量。
  • 自增 ；

原因十分自然：出现在 中的元素一定比当前的 小，而 的倒序枚举，自然使得这些已在权值数组中的元素，在原数组上的索引 大于当前遍历到的索引 。

用例子说明，。

按照 扫：

  • ，查询 前缀和，为 ， 自增 ，。
  • ，查询 前缀和，为 ， 自增 ，。
  • ，查询 前缀和，为 ， 自增 ，。
  • ，查询 前缀和，为 ， 自增 ，。
  • ，查询 前缀和，为 ， 自增 ，。

所以最终答案为 。

注意到，遍历 后的查询 和自增 的两个步骤可以颠倒，变成先自增 再查询 ，不影响答案。两个角度来解释：

  • 对 的修改不影响对 的查询。
  • 颠倒后，实质是在查询 且 的数对数量，而 时不存在 ，所以 相当于 ，所以这与原来的逆序对问题是等价的。

如果查询非严格逆序对（ 且 ）的数量，那就要改为查询 的和，这时就不能颠倒两步了，还是两个角度来解释：

  • 对 的修改 影响 对 的查询。
  • 颠倒后，实质是在查询 且 的数对数量，而 时恒有 ，所以 不相当于 ，与原问题 不等价。

如果查询 且 的数对数量，那这两步就需要颠倒了。

另外，对于原逆序对问题，还有一种做法是正着枚举 ，查询有多少 满足 。做法如下（设 ）：

  • 查询 （ 是 的大小，即 的值域（或离散化后的值域））的区间和。
  • 将 自增 。

原因：出现在 中的元素一定比当前的 大，而 的正序枚举，自然使得这些已在权值数组中的元素，在原数组上的索引 小于当前遍历到的索引 。

树状数组维护不可差分信息

比如维护区间最值等。

注意，这种方法虽然码量小，但单点修改和区间查询的时间复杂度均为 ，比使用线段树的时间复杂度 劣。

区间查询

我们还是基于之前的思路，从 沿着 一直向前跳，但是我们不能跳到 的左边。

因此，如果我们跳到了 ，先判断下一次要跳到的 是否小于 ：

  • 如果小于 ，我们直接把 单点 合并到总信息里，然后跳到 。
  • 如果大于等于 ，说明没越界，正常合并 ，然后跳到 即可。

下面以查询区间最大值为例，给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int getmax(int l, int r) {
  int ans = 0;
  while (r >= l) {
    ans = max(ans, a[r]);
    --r;
    for (; r - lowbit(r) >= l; r -= lowbit(r)) {
      // 注意，循环条件不要写成 r - lowbit(r) + 1 >= l
      // 否则 l = 1 时，r 跳到 0 会死循环
      ans = max(ans, C[r]);
    }
  }
  return ans;
}

可以证明，上述算法的时间复杂度是 。

时间复杂度证明：

考虑 和 不同的最高位，一定有 在这一位上为 ， 在这一位上为 （因为 ）。

如果 在这一位的后面仍然有 ，一定有 ，所以下一步一定是把 的最低位 填为 ；

如果 的这一位 就是 的最低位 ，无论是 还是 ， 的这一位 一定会变为 。

因此， 经过至多 次变换后， 和 不同的最高位一定可以下降一位。所以，总时间复杂度是 。

单点更新

注：请先理解树状数组树形态的以下两条性质，再学习本节。

  • 设 ，则其儿子数量为 ，编号分别为 。
  • 的所有儿子对应 的管辖区间恰好拼接成 。

关于这两条性质的含义及证明，都可以在上一条博客的 [树状数组与其树形态的性质] 一节找到。

更新 后，我们只需要更新满足在树状数组树形态上，满足 是 的祖先的 。

对于最值（以最大值为例），一种常见的错误想法是，如果 修改成 ，则将所有 更新为 。下面是一个反例： 中将 修改成 ，最大值是 ，但按照上面的修改这样会得到 。将 直接修改为 也是错误的，一个反例是，将上面例子中的 修改为 。

事实上，对于不可差分信息，不存在通过 直接修改 的方式。这是因为修改本身就相当于是把旧数从原区间「移除」，然后加入一个新数。「移除」时对区间信息的影响，相当于做「逆运算」，而不可差分信息不存在「逆运算」，所以无法直接修改 。

换句话说，对每个受影响的 ，这个区间的信息我们必定要重构了。

考虑 的儿子们，它们的信息一定是正确的（因为我们先更新儿子再更新父亲），而这些儿子又恰好组成了 这一段管辖区间，那再合并一个单点 就可以合并出 ，也就是 了。这样，我们能用至多 个区间重构合并出每个需要修改的 。

1
2
3
4
5
6
7
8
9
10
void update(int x, int v) {
  a[x] = v;
  for (int i = x; i <= n; i += lowbit(i)) {
    // 枚举受影响的区间
    C[i] = a[i];
    for (int j = 1; j < lowbit(i); j *= 2) {
      C[i] = max(C[i], C[i - j]);
    }
  }
}

容易看出上述算法时间复杂度为 。

建树

可以考虑拆成 个单点修改， 建树。

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

Tricks

建树

以维护区间和为例。

方法一：

每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新自己的直接父亲。

1
2
3
4
5
6
7
8
// Θ(n) 建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

方法二：

前面讲到 表示的区间是 ，那么我们可以先预处理一个 前缀和数组，再计算 数组。

1
2
3
4
5
6
// Θ(n) 建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] = sum[i] - sum[i - lowbit(i)];
  }
}

时间戳优化

对付多组数据很常见的技巧。若每次输入新数据都暴力清空树状数组，就可能会造成超时。因此使用 标记，存储当前节点上次使用时间（即最近一次是被第几组数据使用）。每次操作时判断这个位置 中的时间和当前时间是否相同，就可以判断这个位置应该是 还是数组内的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 时间戳优化
int tag[MAXN], t[MAXN], Tag;

void reset() { ++Tag; }

void add(int k, int v) {
  while (k <= n) {
    if (tag[k] != Tag) t[k] = 0;
    t[k] += v, tag[k] = Tag;
    k += lowbit(k);
  }
}

int getsum(int k) {
  int ret = 0;
  while (k) {
    if (tag[k] == Tag) ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

可以参考的例题