ST表(Sparse Table) 知识点讲解

概念

在信息学竞赛里，有一类题目是：给你一串固定的数据（比如一个班级的考试成绩、一段股票的历史走势、或者一列气温记录），然后问你“从第 $l$ 个到第 $r$ 个之间，最大值是多少？最小值是多少？”。

如果数据量不大，比如只有 10 个数，我们完全可以写个循环，从 $l$ 扫到 $r$，一边扫一边更新最大值或最小值。这叫暴力枚举。

但是，一旦数据量变大了，比如 $n = 10^5$，而且题目还要问你 $m = 10^5$ 次这样的区间问题，暴力枚举每次要跑 $O(n)$ 步，总共就是 $O(nm) \approx 10^{10}$ 步，电脑算到明天也出不了结果，这就是所谓的超时（TLE）。

这时候，我们需要一种更聪明的办法。ST 表（Sparse Table，稀疏表）就是专门为这种只读不改的区间最值问题（也叫 RMQ，Range Minimum/Maximum Query）设计的。它的核心思想是预处理：在回答任何具体问题之前，先花一点时间把一些“标准答案”算好存起来。存好之后，每次查询只需要 $O(1)$（常数时间）就能直接回答，比暴力快得多。

它的代价也很明确：一旦题目里出现了“修改”操作（比如把第 $k$ 个成绩改成 90 分），ST 表就彻底失效了，必须换用线段树。

触发清单（看到这些信号第一时间想到本知识点）

定义

ST 表的核心在于倍增（binary lifting）。我们不存所有可能的区间，只存长度为 $2$ 的幂次的那些区间的最值。因为任意一段区间，都可以被两段长度为 $2$ 的幂次的区间（允许重叠）完全覆盖。

状态定义：

设数组为 $a[1 \dots n]$。定义 $f[i][j]$ 表示从位置 $i$ 开始、长度为 $2^j$ 的区间的最值（以最大值为例，最小值同理，把 max 换成 min）：

$$f[i][j] = \max\{ a[i], a[i+1], \dots, a[i + 2^j - 1] \}$$

也就是说，它管的是 $[i, i + 2^j - 1]$ 这一整段。因为长度只取 $2$ 的幂，$j$ 最大只需要到 $\lfloor \log_2 n \rfloor$，所以第二维大小是 $\log n$。

预处理递推：

边界（$j=0$，长度 $2^0=1$）：

$$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] )$$

• 左边那段：$[i, i + 2^{j-1} - 1]$，正好是 $f[i][j-1]$。
• 右边那段：$[i + 2^{j-1}, i + 2^j - 1]$，正好是 $f[i + 2^{j-1}][j-1]$。
• 两段首尾相接、长度相加 $= 2^{j-1} + 2^{j-1} = 2^j$，无缝拼成整个区间。

循环顺序：先 $j$ 后 $i$（因为 $f[i][j]$ 依赖 $j-1$ 层）。$j$ 从 $1$ 到 $\log n$，$i$ 从 $1$ 到 $n - 2^j + 1$。

查询公式：

对询问 $[l, r]$，长度 $len = r - l + 1$，取 $k = \lfloor \log_2 len \rfloor$（即不超过 $len$ 的最大 $2$ 的幂指数）。把区间拆成两段长度为 $2^k$ 的、可以重叠的区间：

$$ans = \max( f[l][k], \ f[r - 2^k + 1][k] )$$

• 第一段管 $[l, l + 2^k - 1]$。
• 第二段管 $[r - 2^k + 1, r]$。
• 因为 $2^k \le len$，所以这两段加起来的覆盖 $[l, r]$ 绰绰有余（中间允许重叠），取 $\max$ 不受重叠影响。

为什么必须「可重复贡献」：

$\max(x, x) = \max(x)$、$\min(x, x) = \min(x)$、$\gcd(x, x) = x$——这些运算算两遍和算一遍结果一样，叫可重复贡献。ST 表查询时两段重叠，重叠部分被算了两次，所以只有这类运算才安全。

而 区间和 $\text{sum}$ 不行：$\text{sum}$ 重叠部分会被加两次，结果翻倍。区间和请改用前缀和 $s[r] - s[l-1]$。同理，区间乘积（除非保证不溢出且语义允许）一般也不用 ST 表。

选型判据：

技巧速查表（背下来）

例题

例题 1：区间最大值查询

① 题目描述

给定一个长度为 $n$ 的整数数组 $a$（下标从 $1$ 开始），以及 $m$ 次询问。每次询问给出两个整数 $l, r$（$1 \le l \le r \le n$），要求输出子数组 $a[l \dots r]$ 中的最大值。

数据范围：$n, m \le 10^5$，数组元素绝对值不超过 $10^9$。

② 审题分析

• 读题抓条件：静态数组，只查询不修改；询问次数多，单次查询不能太慢。
• 定需求：需要一种能在 $O(1)$ 时间内回答区间最大值的方法。
• 为什么能用本知识点：这是典型的静态区间最值问题（RMQ）。ST 表预处理 $O(n \log n)$，查询 $O(1)$，完美契合。
• 如果不用会怎样：如果用线段树，查询是 $O(\log n)$，总复杂度 $O((n+m)\log n)$，虽然也能过，但常数大且代码长；如果用暴力枚举，单次 $O(n)$，总复杂度 $O(nm) \approx 10^{10}$，绝对超时。

③ 解题思路

1. 读入 $n$ 和 $m$，以及数组 $a$。

2. 预处理 ST 表：

- 第一层 $f[i][0] = a[i]$。

- 外层循环 $j$ 从 $1$ 到 $\lfloor \log_2 n \rfloor$，内层循环 $i$ 从 $1$ 到 $n - 2^j + 1$，递推 $f[i][j] = \max(f[i][j-1], f[i + 2^{j-1}][j-1])$。

3. 预处理对数数组 lg，方便查询时 $O(1)$ 取整：lg[i] = lg[i/2] + 1。

4. 处理 $m$ 次询问：

- 读入 $l, r$。

- 计算 $k = \text{lg}[r - l + 1]$。

- 答案即为 $\max(f[l][k], f[r - 2^k + 1][k])$。

- 输出答案。

④ C++ 完整参考代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

// 定义最大长度 N 和最大幂次 K (2^17 > 100000)
const int N = 100005, K = 18;
int a[N]; // 原始数组
int f[N][K]; // ST 表，f[i][j] 表示从 i 开始长度为 2^j 的区间最大值
int lg[N]; // 预处理对数，lg[i] 表示不超过 i 的最大 2 的幂的指数

int main() {
 // 优化输入输出速度
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n, m;
 if (!(cin >> n >> m)) return 0;

 // 读入数组，同时初始化 ST 表的第一层（长度为 1 的区间）
 for (int i = 1; i <= n; i++) {
 cin >> a[i];
 f[i][0] = a[i];
 }

 // 预处理对数数组 lg[i]
 // lg[1] = 0，因为 2^0 = 1 是 <=1 的最大 2 的幂
 lg[1] = 0;
 for (int i = 2; i <= n; i++) {
 lg[i] = lg[i / 2] + 1;
 }

 // 预处理 ST 表：先枚举长度 j，再枚举起点 i
 // j 从 1 到 lg[n]，因为最大长度不超过 n
 int lim = lg[n];
 for (int j = 1; j <= lim; j++) {
 // 1 << (j-1) 是 2^(j-1)
 int half = 1 << (j - 1);
 // i 的上界要保证 i + 2^j - 1 <= n，即 i <= n - 2^j + 1
 for (int i = 1; i + (1 << j) - 1 <= n; i++) {
 // 递推公式：f[i][j] = max(f[i][j-1], f[i + 2^(j-1)][j-1])
 f[i][j] = max(f[i][j - 1], f[i + half][j - 1]);
 }
 }

 // 处理 m 次查询
 while (m--) {
 int l, r;
 cin >> l >> r;
 // 区间长度
 int len = r - l + 1;
 // 取不超过 len 的最大 2 的幂的指数 k
 int k = lg[len];
 // 两段长度均为 2^k，左段 [l, l+2^k-1]，右段 [r-2^k+1, r]
 // 答案取两段的最大值
 int ans = max(f[l][k], f[r - (1 << k) + 1][k]);
 cout << ans << '\n';
 }

 return 0;
}

⑤ 代码解读（含真实运行输出）

假设输入如下：

5 3
3 1 4 2 5
2 4
1 5
3 3

• 第一层 f[i][0] 为 [3, 1, 4, 2, 5]。
• j=1 时，f[i][1] 为 [3, 4, 4, 5]（对应区间 [1,2], [2,3], [3,4], [4,5] 的最大值）。
• j=2 时，f[1][2] = max(f[1][1], f[3][1]) = max(3, 4) = 4（区间 [1,4] 最大值），f[2][2] = max(f[2][1], f[4][1]) = max(4, 5) = 5（区间 [2,5] 最大值）。
• lg 数组：lg[1]=0, lg[2]=1, lg[3]=1, lg[4]=2, lg[5]=2。

查询过程：

1. 2 4：len = 3，k = lg[3] = 1。

- 左段：f[2][1] = 4（区间 [2,3]）。

- 右段：f[4 - 2 + 1][1] = f[3][1] = 4（区间 [3,4]）。

- ans = max(4, 4) = 4。

2. 1 5：len = 5，k = lg[5] = 2。

- 左段：f[1][2] = 4（区间 [1,4]）。

- 右段：f[5 - 4 + 1][2] = f[2][2] = 5（区间 [2,5]）。

- ans = max(4, 5) = 5。

3. 3 3：len = 1，k = lg[1] = 0。

- 左段：f[3][0] = 4。

- 右段：f[3 - 1 + 1][0] = f[3][0] = 4。

- ans = 4。

程序输出：

4
5
4

与预期完全一致。

例题复盘总结

本题只有一道自构造例题，其核心特征与技巧如下：

共性特征：

• 静态数组，无修改操作。
• 询问次数多，单次查询必须 $O(1)$。
• 目标为区间最值（最大或最小）。

各自技巧：

• 预处理对数数组 lg 避免浮点误差。
• 循环顺序严格为“先 $j$ 后 $i$”。
• 查询右端点公式为 r - (1 << k) + 1，易错点在于漏掉 +1。

审题模板（固定思考流程）：

1. 确认是否“静态”？若有修改，直接放弃 ST 表。

2. 确认是否为“区间最值”？若是，ST 表是首选。

3. 确认数据范围：$n, m$ 是否达到 $10^5$ 级别？若是，暴力必死。

4. 检查是否有“区间和”需求？若有，改用前缀和。

错误清单（仅列特有错误，其余见下节）：

• 查询时右端点算成 r - 2^k 而非 r - 2^k + 1，导致漏掉右端点。
• 预处理循环写成“先 $i$ 后 $j$”，导致依赖未计算的层。
• 使用 log2 浮点函数而未预处理 lg 数组，边界处可能因精度丢失导致 $k$ 少算 1。

写法总表

分工说明：触发清单用于快速判断“何时想到 ST 表”；技巧速查表用于记忆具体实现细节；写法总表则按逻辑层次梳理核心代码片段，便于对照检查。

常见错误

1. 把区间和也用 ST 表：错。$\text{sum}$ 重叠部分会被加两次，结果翻倍。区间和必须用前缀和 $s[r] - s[l-1]$，或者带修改时用树状数组/线段树。

2. 预处理循环写成「先 $i$ 后 $j$」：错。$f[i][j]$ 依赖 $j-1$ 层的值，必须先枚举 $j$。顺序写反会导致用到还没算好的值，结果全错。

3. 查询右端点算成 r - 2^k 而不是 r - 2^k + 1：差一个 +1，区间覆盖不到右端点，答案偏小甚至越界。记住起点是 r - 2^k + 1。

4. 认为两段不能重叠：恰恰相反，ST 表故意允许重叠，只要覆盖整段即可；这也正是它只支持可重复贡献运算的原因。

5. 题目有修改还用 ST 表：ST 表是静态结构，任何「单点改 / 区间改」都应换线段树。看到修改标记先排除 ST 表。

6. log2 浮点误差导致 $k$ 少算 1：边界上 $\log_2(\text{整数})$ 可能因精度变成 $k-1.999\dots$ 被 $\lfloor \cdot \rfloor$ 成 $k-1$。用整数预处理的 lg 数组更稳。

自测

1. 默写 $f[i][j]$ 的定义，并写出预处理递推式与查询式（用 $\max$）。

2. 数组 $a = [5, 2, 9, 1, 7]$，手算 $f[2][1]$ 和查询 $\max(1, 4)$ 的结果，并说明两段怎么覆盖。

3. 为什么 ST 表查询要把区间拆成「可重叠」的两段？如果换成区间和，重叠会出什么问题？

4. 判断题：ST 表能支持「把 $a[3]$ 改成 $8$ 之后再查询」吗？（ ）为什么？

5. 下面哪个不适合用 ST 表，改用什么？(a) 静态区间最小值；(b) 静态区间和；(c) 带单点修改的区间最大值。

6. 查询 $[l, r]$ 时，$k$ 应该怎么取？若 $\text{len} = 7$，$k$ 是多少？两段分别覆盖哪些下标？

7. 预处理的时间复杂度为什么是 $O(n \log n)$，查询为什么是 $O(1)$？

举一反三 · 审题流水线

拿到一道区间题，先别急着写代码，按下面顺序过一遍： 1. 看修改：题干里有没有“把第 $k$ 个数改成 $x$”或者“区间加 $y$”？有 → 直接放弃 ST 表，转线段树/树状数组。 2. 看目标：是求最值（最大/最小）、GCD、LCA 还是求和？ - 最值/GCD/LCA → 静态的话优先 ST 表。 - 求和 → 静态用前缀和，带修改用树状数组。 3. 看数据量：$n, m$ 是否达到 $10^5$ 级别？若是，暴力枚举必死，必须上 $O(1)$ 或 $O(\log n)$ 的解法。 4. 看边界：区间长度可能为 1，此时 $k = \lg 1 = 0$，要确保代码里 $f[i][0]$ 初始化正确，且查询公式里 $r - 2^k + 1$ 能正常工作。 5. 最后检查：预处理循环顺序是不是“先 $j$ 后 $i$”？查询时 $k$ 是不是用预处理的 lg 数组取的？右端点有没有漏掉 +1？

练手题

题 1：区间最小值

给定一个长度为 $n$ 的整数数组 $a$（$1 \le a[i] \le 10^9$），以及 $m$ 次询问。每次询问给出 $l, r$，要求输出 $a[l \dots r]$ 中的最小值。

数据范围：$n, m \le 10^5$。

提示：将 ST 表中的 $\max$ 换成 $\min$ 即可，其余逻辑完全相同。

题 2：区间 GCD

给定一个长度为 $n$ 的正整数数组 $a$，以及 $m$ 次询问。每次询问给出 $l, r$，要求输出 $a[l \dots r]$ 中所有数的最大公约数（GCD）。

数据范围：$n, m \le 10^5$，$a[i] \le 10^9$。

提示：C++17 提供了 std::gcd 函数（头文件 <numeric>），ST 表同样适用，因为 $\gcd(x, x) = x$ 满足可重复贡献。