ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。

它主要应用倍增的思想，可以实现 预处理 $O(n\log n)$ 、 查询 $O(1)$ 。根据它的时间复杂度可以看出，它主要用于区间值保持不变，需要多次查询区间中的最大值最小值的问题。这里其实不只是最大值最小值问题，还可以解决 $ST(x, x) = x$ 的相关函数的问题（这种问题叫做「可重复贡献问题」），最大值最小值其实也是 $\max(x, x) = x$ ，而 $gcd(x, x) = x$ 也是其中一种。

所谓RMQ问题，以最大值为例，是假如有一个数列 $A$，给你一个区间 $[l, r]$ ，要求 $\max\limits_{i \in [l, r]} A_i$。

ST表的实际含义

ST表使用一个二维数组ST[i][j]，对于范围内的所有ST[i][j]，先算出并存储 $\max\limits_{[i,i+2^j)}$（本文中的区间都是离散意义下的，只包含整数，所以此区间也可以写成 $[i, i+2^j-1]$​​ ），这称为预处理。查询时，再利用这些子区间算出待求区间的最大值。

为了更加直观地理解ST[i][j]的实际含义，这里给出一个直观的例子：

假设有8个数据：4 5 1 6 8 0 2 9。要找出区间里的最大值。可以这样判断：

image-20240304194604703

上图只是示例，没有全部写出来，比如：ST[1][1]=5,ST[3][1]=8,ST[1][2]=8,ST[2][2]=8等。

因此可以看出：ST[i][j]表示从下标 $i$ 开始的，包含 $2^j$ 个元素的区间的最大值（最小值）。这个ST数组实际上即使ST表。

预处理

上面讲到了最核心的部分，ST表的内容，那么如何预处理出来呢？

其实通过上图也能看出，ST[0][1]与ST[0][0]和ST[1][0]是有关联的，ST[0][2]与ST[0][1]，ST[2][1]是有关联的。于是可以想到动态规划的方法来预处理，状态就是ST[i][j]，状态是从ST[i][j-1]和ST[i+(1<<(j-1))][j-1]转移过来的。

即，动态转移方程为（求区间最大值时）：ST[i][j] = max(ST[i][j-1], ST[i+(1<<(j-1))][j-1])

这里的1<<(j-1)等价于 $2^{j-1}$ 。如果这里看不懂，应该先去补一下位运算的基础啦。

更直观理解：

image-20240304185231783

这里要尤其注意，实际上数组的索引是离散的，因此会有减1。

「预处理的模版代码」：

（以求区间最大值为例）

1
2
3
4
5
int ST[N][20];
for (int i = 0; i < n; ++i) cin >> ST[i][0];
for (int j = 1; (1<<j) < n; ++j)
    for (int i = 0; i+(1<<j)-1 < n; ++i)
        ST[i][j] = max(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);

注意，这里的外层循环是j，内层循环才是i。

为什么外层循环要是j？

根据图一理解，j表示的其实是图中的行，比如令ST[0][0]所在行为第0行，ST[0][1]所在行为第1行。可以看出，第j行的更新需要第j-1的值。

$2^{20}=1048576>1e^{6}$,$2^{18}=262144>2e^5$ ，根据经验，一般开20就够了。

如何查询

假设需要查询区间 $[l, r]$ 中的最大值。其实就是要找到两个子区间，这两个子区间的并集的元素个数为$r-l+1$个。通常$r-l+1$不会刚好等于$2^s$,于是我们要考虑更通用的情况。

假设 $2^{q} < r-l+1 < 2^{q+1}$ ，那么区间 $[l, r]$ 就可以用两个区间（ $[l, l+2^q-1]$,$[r-2^q+1,r]$ ）的并集表示。根据 $\max$ 的性质（可重复贡献问题的性质），可知:

那么这个 $q$ ​如何求呢？

这里用一个小技巧：预处理一个Log2数组，其中Log2[i]表示q满足 $2^q < Log2[i] < 2^{q+1}$ 。

怎么预处理？

1
2
int Log2[N];
for (int i = 2; i < n; ++i) Log2[i] = Log2[i >> 1] + 1;

不过也可以不预处理，可以直接用函数：std::__lg()，__lg(i)的含义与Log2[i]相同。

不过我更喜欢自己预处理，感觉会快一点。

这样就能求出左区间为：ST[l][q]，右区间为：ST[r-(1<<q)+1][q]

「查询代码模版」：

1
2
3
4
int query(int l, int r) {
    int q = __lg(r-l+1);
    return max(ST[l][q], ST[r-(1<<q)+1][q]);
}
1
2
3
4
int query(int l, int r) {
    int q = Log2[r-l+1];
    return max(ST[l][q], ST[r-(1<<q)+1][q]);
}

整体模版

1
2
3
4
5
6
7
8
9
10
11
12
int ST[N][__lg(N)+1];
void init(int n) {
    for (int i = 0; i < n; ++i) f[i][0] = A[i]; //这里一般可以直接输入
    for (int j = 1; j < __lg(n); ++j)
        for (int i = 0; i+(1<<j)-1 < n; ++i)
            ST[i][j] = max(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);
}

int query(int l, int r) {
    int q = __lg(r-l+1);
    return max(ST[l][q], ST[r-(1<<j)+1][r]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
int ST[N][20], Log2[N];

void init() {
	for (int i = 2; i <= n; ++i) Log2[i] = Log2[i>>1]+1;
	for (int j = 1; (1<<j) <= n; ++j) 
		for (int i = 1; i+(1<<j)-1 <= n; ++i)
			stmax[i][j] = max(stmax[i][j-1], stmax[i+(1<<(j-1))][j-1]);
}

int query(int l, int r) {
	int s = Log2[r-l+1];
	return max(stmax[l][s], stmax[r-(1<<s)+1][s]);
}

例题

「题目链接」：[USACO07JAN] Balanced Lineup G

「题目描述」：

农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 200,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.

「输入格式」：

第一行输入两个正整数 $N$ , $Q$ ，表示 $N$ 头牛，和 $Q$ 个可能的牛的选择

接下来N行，输入一个正整数，表示牛的身高

接下来Q行，输入两个正整数 $A$ , $B$ ，表示从 $A$ 到 $B$ 的所有牛($0 \le A \le B \le N$)

「输出格式」：

输出Q行，表示Q个可能的牛的选择中的每一组身高极差。

「样例输入」：

1
2
3
4
5
6
7
8
9
10
6 3
1
7
3
4
2
5
1 5
4 6
2 2

「样例输出」：

1
2
3
6
3
0

「实现代码」：

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
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e4+5;

int n, q;
int stmax[N][20], stmin[N][20]; // stmax存储区间最大值，stmin存储区间最小值
int Log2[N];

void init() {
	for (int i = 2; i <= n; ++i) Log2[i] = Log2[i>>1]+1;
	for (int j = 1; (1<<j) <= n; ++j) 
		for (int i = 1; i+(1<<j)-1 <= n; ++i) {
			stmax[i][j] = max(stmax[i][j-1], stmax[i+(1<<(j-1))][j-1]);
			stmin[i][j] = min(stmin[i][j-1], stmin[i+(1<<(j-1))][j-1]);
		}
}

int query(int l, int r) {
	int s = Log2[r-l+1];
	return max(stmax[l][s], stmax[r-(1<<s)+1][s]) - min(stmin[l][s], stmin[r-(1<<s)+1][s]);
}

int main() {
	cin >> n >> q;
	// 牛的编号和询问都是从1开始的，这里直接把下标0空出来
	for (int i = 1; i <= n; ++i) {
		cin >> stmin[i][0];
		stmax[i][0] = stmin[i][0];
	}

	init();

	int a, b;
	while (q--) {
		cin >> a >> b;
		cout << query(a, b) << endl;
	}

	return 0;
}

提交通过：

截屏2024-03-04 20.28.17