Sparse Table (ST 表) 详解

ST 表 — 静态区间最值问题（RMQ）利器。能够做到 $O(n \log n)$ 预处理，$O(1)$ 查询，比线段树单次查询复杂度低（而且更好写）。

对于那些专门卡线段树的 RMQ，首选的就是 ST 表。

介绍

就以查询区间最大值为例吧。模板题传送门 下面是一个 ST 表的例子。

乍看上去不知道是什么东西。不过我们注意到，f 数组的第 0 行是和 a 数组（即要查询的数组是一样的），这就是初始化后的 f 数组（即存储 ST 表的二维数组）（其实 f[0][] 就能当 a 数组用） 接下来的每行每一个数 $f_{i,j}$，表示从下标从 $j$ 开始长度为 $2^i$ 的区间 $[j, j+2^i)$ 内的最大值。 比如 $f_{1,1}$，表示从下标从 $1$ 开始，区间长度为 $2^1$（即 $2$）这段区间 $[1,3)$ 的最大值； 同理 $f_{1,2}$，表示的是从下标为 $2$ 开始的长度为 $2$ 的区间 $[2,4)$ 的最大值。 下一行也是，$f_{2,1}$表示的则是区间长度为 $2^2$（即 $4$）的。

我们还注意到，f 数组的最大行号和 $\log_2N$ 一样，这是因为 ST 表利用的倍增思想，每一行的区间长度都会是上一行的两倍。

预处理

思路

像这样的表格如何预处理呢？ 为了方便利用上次的结果，我们把 f 数组的第 0 行赋值为 a 数组。

因为最大行号和 $\log_2N$ 一样，所以最外层要循环这么多次。 内层循环进行 f 数组第 i 行的填充。 利用上一行的数据，取 f[i - 1][j] 和 f[i - 1][j + (1 << (i - 1))] 的最大值。（如下图中颜色所标注的）

如何理解这个转移？ 就拿第 1 行向第 2 行转移为例。

因为上一行的第 $j$ 个数保存了下标从 $j$ 开始且长度为 $2$ 区间内的最大值，所以转移的时候只需要比较这两个区间中最大值的大小就可以了。

同理，在第 2 行向第 3 行转移时，也是像这样。

向这样转移的时候，求最小值时要记得把 f 数组的空白位置填充为一个极大值(INF)，反过来要求最大值时要填充为一个极小值。

代码

int logn = log2(n);
for (int i = 1; i <= logn; i++)
	for (int j = 1; j + (1 << i) - 1 <= n; j++)
		f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);

查询

思路

查询和预处理基本上一致，因为预处理本质上就是利用上一行的信息查询区间 $[j, j+2^i)$ 最大值并填充到当前格子。

只是有区别的地方在于，预处理的区间没有重叠，而查询时的区间可能有重叠，然而这并不影响我们查询区间最大值。

所以查询区间最大值就是取适合当前区间长度（即 $\log_2(r-l+1)$）的行来进行。

代码

int query(int l, int r) {
	int k = log2(r - l + 1);
	return max(f[k][l], f[k][r - (1 << k) + 1]);
}

完整代码

代码中直接把 f 数组的第 0 行当做 a 数组。

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
int n, m;
int f[20][maxN];
void init() {
    int logn = log2(n);
	for (int i = 1; i <= logn; i++)
		for (int j = 1; j + (1 << i) - 1 <= n; j++)
			f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
	int k = log2(r - l + 1);
	return max(f[k][l], f[k][r - (1 << k) + 1]);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &f[0][i]);
	init();
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", query(a, b));
	}
	return 0;
}