跳转至

倍增表（ST表，sparse table）

简介

sparse table 是一种通过预处理快速查询静态数据的数据结构，一般用于解决RMQ问题。基于倍增和动态规划的思想，预处理的时间复杂度为 \(O(Nlog_2^N)\)，根据查询数据性质的不同，可以在 \(O(log_2^N)\) 甚至 \(O(1)\) 的时间复杂度内回答每个询问。

预处理

每个十进制的正整数都可以用二进制表示，基于二进制和十进制之间的转换规则，任何正整数都可以用 \(2\) 的不同次幂之和表示，例如：

\[ 19=10011^2=2^4+2^1+2^0=19 \]

类似的，任何区间 \([l, r]\) 都可以被拆成更小的用 \(2\) 的幂形式表示的区间的并集：

\[ \begin{aligned} {}[5, 17] &= [5,5+2^3-1] \cup [13,13+2^2-1] \cup [17,17+2^0-1] \\ &= [5,12] \cup [13,16] \cup [17,17] \end{aligned} \]

试想，如果我们事先把所有用到的子集区间的答案（例如最大值、最小值、区间和、最大公约数、最小公倍数等）计算出来（时间复杂度显然为 \(O(Nlog_2^N)\)），就可以利用计算出来的小区间答案组合为需要查询的某个大区间的答案，时间复杂度为 \(O(log_2N)\)。

预处理过程

设 \(f[i][j]\) 表示数组 \(A\) 中下标在子区间 \([i, i + 2^j - 1]\) 里的最大值，也就是从 \(i\) 开始的 \(2^j\) 个数的最大值。显然，\(f[i][0] = A[i]\)。

接下来，通过下面的动态规划递推公式把子区间的长度成倍增长，即长度为 \(2^j\) 的子区间的最大值是左右两半长度为 \(2^{j-1}\) 的子区间的最大值中较大的一个。

\[ f[i][j] = max(f[i][j-1],f[i+2^{j-1}][j-1]) \]

设输入数据数组 A[13] = {4, 2, 3, 7, 1, 5, 3, 3, 9, 6, 7, -1, 4}，求数组在某个区间的最大值。

让 \(N\) 为数组的长度 \(13\)，\(P\) 为使 \(2^P \leq N\) 成立的最大值，也就是 \(P = floor(log_2^N) = floor(log_2^{13}) = 3\)。

记住：\(f[i][j]\) 表示数组 \(A\) 中下标在子区间 \([i,i+2^j-1]\) 里最大的值。

先求出 \(max(i \sim i + 2^0 - 1) = f[i][0] = A[i]\)

再求出 \(max(i \sim i + 2^1 - 1) = max(f[i][0], f[i + 1][0])\)

再求出 \(max(i \sim i + 2^2 - 1) = max(f[i][1], f[i + 2][1])\)

再求出 \(max(i \sim i + 2^3 - 1) = max(f[i][2], f[i + 4][2])\)

\(\vdots\)

下标\(\downarrow\) 值\(\downarrow\) \(2^0\) \(2^1\) \(2^2\) \(2^3\)
1 4 4 4 7 7
2 2 2 3 7 9
3 3 3 7 7 9
4 7 7 7 7 9
5 1 1 5 5 9
6 5 5 5 9 9
7 3 3 3 9 9
8 3 3 9 9 9
9 9 9 9 9 9
10 6 6 7 7 7
11 7 7 7 7 7
12 -1 -1 4 4 4
13 4 4 4 4 4

todo: 添加递推动画gif

这样，我们就有了预处理完成的ST表了。

查询

由于查询时是把分割的小区间答案合并成大区间答案，所以所查询的数据规则必须符合结合律(associative property)才能得到正确答案。

\[ f(f(a, b), c) = f(a, f(b, c)) \]

显然，如果规则 \(f\) 是加法运算的话，结合律是成立的，因为 \((a+b)+c=a+(b+c)\)。同样的，最大值、最小值，区间和、最大公约数、最小公倍数都是满足结合律的，而减法运算不符合结合律，因为 \((a-b)-c \neq a-(b-c)\)。

满足结合律的运算规则
  • \(f(a,b)=a+b\)
  • \(f(a,b)=a \times b\)
  • \(f(a,b)=max(a,b)\)
  • \(f(a,b)=min(a,b)\)
  • \(f(a,b)=gcd(a,b)\)
  • \(f(a,b)=lcm(a,b)\)
不满足结合律的运算规则
  • \(f(a,b)=a-b\)
  • \(f(a,b)=a\ /\ b\)
  • \(f(a,b)=a\ \%\ b\)

符合结合律运算规则的查询可以在 \(O(log_2^N)\) 的时间复杂度内完成。如果查询问题同时属于可重复贡献问题（overlap friendly）的话，时间复杂度可以更进一步缩短到 \(O(1)\)。

\[ f(f(a,b),f(b,c))=f(a,f(b,c)) \]
可重复贡献问题

可重复贡献问题是指对于运算 \(\operatorname{opt}\)，满足 \(x\operatorname{opt} x=x\)，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 \(\max(x,x)=x\)，gcd 有 \(\operatorname{gcd}(x,x)=x\)，所以 RMQ(区间最大/最小值查询) 和区间 GCD 就是一个可重复贡献问题。但区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这样计算的结果是不准确的。另外，\(\operatorname{opt}\) 还必须满足结合律才能使用 ST 表求解。

举例说明。

定义 \(f(a,b)=max(a,b)\)，由于

\[ max(max(x,y),max(y,z))=max(x,max(y,z))=max(x,y,x) \]

所以求最大值（或最小值）是一个可重复贡献问题。

定义 \(f(a,b)=a+b\)，由于

\[ (x+y)+(y+z) \neq x+(y+z) \]

所以求和运算不是一个可重复贡献问题。

可重复贡献问题
  • \(f(a,b)=1 \times b\)
  • \(f(a,b)=min(a,b)\)
  • \(f(a,b)=max(a,b)\)
  • \(f(a,b)=(a \times b)\ /\ a, a \neq 0\)
  • \(f(a,b)=gcd(a,b)\)
非可重复贡献问题
  • \(f(a,b)=a \times b\)
  • \(f(a,b)=a+b\)
  • \(f(a,b)=a-b\)
例题1

给定一个长度为 \(N\) 的数列，共有 \(M\) 次询问，每次询问给定两个整数 \(l_i\) 和 \(r_i\) 代表询问区间，求每次询问区间内数列的最大值，其中 \(0 \leq N \leq 10^5\)，\(0 \leq M \leq 10^5\)。

 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
34
35
36
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 100010;
//const int T = log(N) / log(2) + 1;
int a[N], f[N][17];
int n, m;

// 预处理ST表函数
void ST_prework() {
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    int t = (int)(log(n) / log(2) + 1);
    for (int j = 1; j < t; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

// 查询函数
int ST_query(int l, int r) {
    int k = (int)(log(r - l + 1) / log(2));
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    ST_prework();
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n" , ST_query(l, r));
    }
    return 0;
}

todo: 笛卡尔树 \(O(n)\) 线性时间复杂度求 RMQ

最后更新: 2021-09-29
Back to top