OI-wiki 稀疏表（Sparse Table）完全指南：可重复贡献问题的 Θ(1) 区间查询利器

OI-wiki 稀疏表（Sparse Table）完全指南：可重复贡献问题的 Θ(1) 区间查询利器

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

稀疏表（Sparse Table，简称 ST 表）是 OI-wiki 数据结构章节中用于解决可重复贡献问题（如区间最大值 RMQ、区间按位与/或、区间 GCD）的高效数据结构，它以 $\Theta(n\log n)$ 的时间完成预处理、$\Theta(1)$ 的时间回答每个区间询问，且不支持修改。本文以 sparse-table.md 为骨架，结合仓库内的 C 风格实现、C++ 风格类封装、Python 实现 及配套样例数据，系统讲解 ST 表的定义、倍增原理、预处理与查询流程、工程化注意点，以及其维护区间 GCD 等扩展信息时的复杂度分析，帮助你在海量询问场景下写出可运行的完整代码。

定义：可重复贡献问题与 RMQ

ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。

!!! note "什么是可重复贡献问题？" 可重复贡献问题是指对于运算 $\operatorname{opt}$，满足 $x\operatorname{opt} x=x$，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 $\max(x,x)=x$，gcd 有 $\operatorname{gcd}(x,x)=x$，所以 RMQ 和区间 GCD 都是可重复贡献问题。像区间和就不具有这个性质：如果求区间和时采用的预处理区间发生了重叠，重叠部分会被计算两次，这是我们所不愿意看到的。另外，$\operatorname{opt}$ 还必须满足结合律，才能使用 ST 表求解。

!!! note "什么是 RMQ？" RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。解决 RMQ 问题有很多种方法，可以参考仓库中的 RMQ 专题。

可重复贡献性质是 ST 表能做到 $\Theta(1)$ 查询的根基：只要用来求解的预处理区间并集覆盖了询问区间，即使区间之间存在重叠，最终答案依然正确。这使得查询时可以用两个（至多）预处理区间覆盖整个询问区间。

引入：模板问题与暴力做法的局限

!!! example "[Luogu P3865【模板】ST 表 & RMQ 问题]" 给定 $n$（$1\le n\le 10^5$）个整数，有 $m$（$1\le m\le 2\times 10^6$）个询问，对于每个询问，你需要回答区间 $[l,r]$ 中的最大值。

考虑暴力做法：每次都对区间 $[l,r]$ 扫描一遍求出最大值。在 $m$ 高达 $2\times 10^6$ 而 $n$ 为 $10^5$ 的数据规模下，总复杂度为 $\Theta(nm)$，显然会超时。仓库在 sparse-table 示例目录 中提供了该模板题的小型样例：输入 sparse-table_1.in 给出了 8 个元素9 3 1 7 5 6 0 8与 8 个询问，期望输出 sparse-table_1.ans，可用于快速验证实现正确性。

ST 表的倍增思想与预处理

ST 表基于倍增思想，可以做到 $\Theta(n\log n)$ 预处理、$\Theta(1)$ 回答每个询问，但不支持修改操作。

为什么普通倍增不够快

基于倍增思想，我们考虑如何求出区间最大值。如果按照一般的倍增流程，每次跳 $2^i$ 步，询问时的复杂度仍旧是 $\Theta(\log n)$，并没有比线段树更优，反而预处理一步还比线段树慢。这是 ST 表设计上需要避免的。

利用可重复贡献性质降复杂度

我们发现 $\max(x,x)=x$，即区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。手动模拟可以发现：我们能用至多两个预处理过的区间来覆盖询问区间，询问时间复杂度因此被降至 $\Theta(1)$，在处理有大量询问的题目时十分有效。

状态设计与转移方程

具体实现如下：

令 $f(i,j)$ 表示区间 $[i,i+2^j-1]$ 的最大值。

• 显然 $f(i,0)=a_i$，即长度为 1 的区间最大值就是元素本身；
• 根据定义式，第二维相当于倍增的时候「跳了 $2^j-1$ 步」。依据倍增思路，写出状态转移方程：

$$ f(i,j)=\max\bigl(f(i,j-1),,f(i+2^{j-1},j-1)\bigr) $$

即长度为 $2^j$ 的区间被拆成两个长度为 $2^{j-1}$ 的子区间：左半区间 $[i,i+2^{j-1}-1]$ 与右半区间 $[i+2^{j-1},i+2^j-1]$。

查询：两个区间覆盖一个询问

对于每个询问 $[l,r]$，把它分成两部分：$[l,l+2^s-1]$ 与 $[r-2^s+1,r]$，其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$。两部分结果取最大值即为回答。由于最大值是「可重复贡献问题」，两个区间之间的重叠不会影响结果；又因为这两个区间完全覆盖了 $[l,r]$，答案的正确性得以保证。

三种参考实现对照

仓库为 P3865 提供了三种参考实现，分别展示了过程式、面向对象式与 Python 三种写法，核心逻辑完全一致。

C 风格实现（数组 + 全局变量）

见 sparse-table_1.cpp：

#include <algorithm> #include <iostream> using namespace std; constexpr int N = 100000 + 5; constexpr int logN = 16; // ⌊ log_2 N ⌋ int f[logN + 1][N], Logn[N]; // 初始化对数值 void pre() { Logn[2] = 1; for (int i = 3; i < N; i++) { Logn[i] = Logn[i / 2] + 1; } } int main() { cin.tie(nullptr)->sync_with_stdio(false); pre(); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> f[0][i]; for (int j = 1; j <= logN; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]); // ST表具体实现 for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; int s = Logn[y - x + 1]; cout << max(f[s][x], f[s][y - (1 << s) + 1]) << '\n'; } return 0; }

该实现使用 1-based 下标，二维数组第一维是倍增层数、第二维是起点，通过Logn数组预处理 $\lfloor\log_2 x\rfloor$，查询时直接以 $O(1)$ 查表得到 $s$。

C++ 风格实现（模板类封装，可替换运算）

见 sparse-table_2.cpp：

#include <algorithm> #include <functional> #include <iostream> #include <vector> #if defined(_MSC_VER) && !defined(__clang__) #include <immintrin.h> #define __builtin_clz _lzcnt_u32 #endif using namespace std; // 使用内建函数计算 ⌊ log_2 x ⌋ int lg2(int x) { return 31 - __builtin_clz(x); } template <typename T> class SparseTable { using VT = vector<T>; using VVT = vector<VT>; using func_type = function<T(const T &, const T &)>; VVT ST; static T default_func(const T &t1, const T &t2) { return max(t1, t2); } func_type op; public: SparseTable(const vector<T> &v, func_type _func = default_func) { op = _func; int n = v.size(), l = lg2(n); ST.assign(l + 1, VT(n, 0)); for (int i = 0; i < n; ++i) ST[0][i] = v[i]; for (int j = 1; j <= l; ++j) for (int i = 0; i + (1 << j) <= n; ++i) ST[j][i] = op(ST[j - 1][i], ST[j - 1][i + (1 << (j - 1))]); } T query(int l, int r) { int q = lg2(r - l + 1); return op(ST[q][l], ST[q][r - (1 << q) + 1]); } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, m; cin >> n >> m; vector<int> a(n); for (int &i : a) cin >> i; SparseTable<int> st(a); for (int i = 1; i <= m; ++i) { int x, y; cin >> x >> y; cout << st.query(x - 1, y - 1) << '\n'; } return 0; }

这个版本有三个值得注意的设计点：

1. 运算可注入：构造函数接受func_type _func参数，默认为max。这意味着只需更换运算函数，同一个类即可用于区间按位与、按位或、区间 GCD 等其他可重复贡献运算（前提是该运算满足结合律与 $x\operatorname{opt}x=x$）。
2. 内建函数求对数：lg2使用__builtin_clz在 $O(1)$ 内得到 $\lfloor\log_2 x\rfloor$，且对 MSVC 编译器做了宏兼容处理（映射为_lzcnt_u32），体现了跨平台考虑。
3. 0-based 下标：外部调用时query(x - 1, y - 1)，与 1-based 的 C 版本形成对照。

Python 实现

见 sparse-table_1.py：

import sys input = sys.stdin.readline class SparseTable: def __init__(self, arr: list, func=min): self.func = func self.n = len(arr) self.log = [0] * (self.n + 1) for i in range(2, self.n + 1): self.log[i] = self.log[i // 2] + 1 self.k = self.log[self.n] self.st = [[0] * (self.n) for _ in range(self.k + 1)] self.st[0] = arr for j in range(1, self.k + 1): i = 0 while i + (1 << j) <= self.n: self.st[j][i] = self.func( self.st[j - 1][i], self.st[j - 1][i + (1 << (j - 1))] ) i += 1 def query(self, left: int, right: int): j = self.log[right - left + 1] return self.func(self.st[j][left], self.st[j][right - (1 << j) + 1]) n, m = map(int, input().split()) a = list(map(int, input().split())) st = SparseTable(a, max) for _ in range(m): left, right = map(int, input().split()) print(st.query(left - 1, right - 1))

Python 版本同样支持注入func（示例中传入max求区间最大值），其log数组的递推log[i] = log[i // 2] + 1与 C 版本Logn数组的构造方式一一对应，可交叉印证算法的一致性。

样例验证

用仓库自带的样例可以快速验证任意一种实现：输入 sparse-table_1.in（与 sparse-table_2.in 内容相同）：

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

期望输出 sparse-table_1.ans（与 sparse-table_2.ans 相同）：

9 9 7 7 9 8 7 9

工程化注意点

1. 输入输出优化：此类题目输入输出数据量一般很大（如 $m\le 2\times 10^6$），建议开启输入输出优化。三种参考实现均使用了cin.tie(nullptr)->sync_with_stdio(false)（或 Python 的sys.stdin.readline）来加速 IO，这一点在编写时不可省略。

2. 数组维度与缓存局部性：预处理 ST 表时通常需要建立一个一维大小为 $\log n$、另一维大小为 $n$ 的数组。此时应优先让大小为 $\log n$ 的维度作为第一维（即f[logN + 1][N]而非f[N][logN + 1]），以提升缓存局部性。C 风格实现 sparse-table_1.cpp 正是按f[logN + 1][N]声明的。

3. 对数计算：每次用std::log重新计算对数函数值并不值得，建议利用__builtin_clz或__lg等内建函数进行计算（见 sparse-table_2.cpp 中的lg2）。若无法利用这些内建函数，也可以预处理对数函数值，递推方式如下：

$$ \begin{cases} \texttt{Logn}[1] \gets 0, \ \texttt{Logn}[i] \gets \texttt{Logn}\left[\frac{i}{2}\right] + 1. \end{cases} $$

C 风格实现的pre()函数即为该递推的直接落地：它从Logn[2] = 1开始，对 $i=3..N-1$ 执行Logn[i] = Logn[i / 2] + 1。

ST 表维护其他信息：按位与、按位或与区间 GCD

除 RMQ 以外，还有其他「可重复贡献问题」。例如「区间按位与」「区间按位或」「区间 GCD」，ST 表都能高效地解决——只需把运算函数替换为&、|或gcd即可，上述 C++ 模板类与 Python 类天然支持这种替换。

对于「区间 GCD」，需要特别说明其复杂度特征：

• ST 表维护「区间 GCD」的查询复杂度为 $\Theta(\log w)$（令值域为 $w$），而线段树为 $\Theta(\log n+\log w)$。由于值域一般大于 $n$，ST 表的查询复杂度并没有比线段树更优；
• 但 ST 表的预处理复杂度也没有比线段树更劣，且编程复杂度方面 ST 表比线段树简单很多。

从结构上分析，「可重复贡献问题」一般都带有某种类似 RMQ 的成分：例如「区间按位与」就是每一位取最小值（按位与即逐位 min），而「区间 GCD」则是每一个质因数的指数取最小值（质因数分解后按指数逐项取 min）。这一观察有助于快速判断一个新问题是否适合用 ST 表解决。

附录：ST 表求区间 GCD 的时间复杂度分析

直观分析

在算法运行时，可能要经过 $\Theta(\log n)$ 次迭代，每一次迭代都可能使用 GCD 函数进行递归。令值域为 $w$，GCD 函数的时间复杂度最高是 $\Omega(\log w)$，所以总时间复杂度看似是 $O(n\log n\log w)$。

但在 GCD 过程中，每一次递归（除最后一次递归之外）都会使数列中的某个数至少减半，而数列中的数最多减半的次数为 $\log_2(w^n)=\Theta(n\log w)$。因此 GCD 的递归部分最多只会运行 $O(n\log w)$ 次，再加上循环部分（以及最后一层递归）的 $\Theta(n\log n)$，最终时间复杂度为 $O(n(\log w+\log n))$。由于可以构造数据使时间复杂度达到 $\Omega(n(\log w+\log n))$，所以最终时间复杂度即为 $\Theta(n(\log w+\log n))$。

查询部分的时间复杂度很好分析：考虑最劣情况，即每次询问都询问最劣的一对数，时间复杂度为 $\Theta(\log w)$。因此 ST 表维护「区间 GCD」的时间复杂度为：预处理 $\Theta(n(\log n+\log w))$，单次查询 $\Theta(\log w)$。

作为对照，线段树的相应操作是：预处理 $\Theta(n\log w)$，单次查询 $\Theta(\log n+\log w)$。

更严谨的势能分析证明

理解本段，可能需要具备时间复杂度章节中关于「势能分析法」的知识。

先分析预处理部分的时间复杂度。设「待考虑数列」为预处理 ST 表时当前层循环的数列：例如第零层的数列就是原数列，第一层的数列就是第零层数列经过一次迭代之后的数列，即st[1..n][1]，记为 $A$。

定义势能函数为「待考虑数列」中所有数的累乘以 2 为底的对数：

$$ \Phi(A)=\log_2\left(\prod_{i=1}^{n} A_i\right) $$

在一次迭代中，所花费的时间为迭代循环所花费的时间与 GCD 所花费的时间之和。GCD 花费的时间有长有短：最短可能只有两次甚至一次递归，最长可能有 $O(\log w)$ 次递归。但是，GCD 过程中除最开头一层与最末一层以外，每次递归都会使「待考虑数列」中的某个结果至少减半，即 $\Phi(A)$ 至少减少 1，该层递归所用的时间可以被势能函数均摊。

同时，$\Phi(A)$ 的初值最大为 $\log_2(w^n)=\Theta(n\log w)$，且 $\Phi(A)$ 不增。因此 ST 表预处理部分的时间复杂度为 $O(n(\log w+\log n))$。

总结与习题

ST 表能够较好地维护「可重复贡献」的区间信息（同时还应满足结合律），时间复杂度较低、代码量相对其他算法很小。但它的短板同样明显：能维护的信息非常有限，不能较好地扩展，并且不支持修改操作——一旦涉及单点修改或区间修改，应转而考虑线段树、树状数组等可维护动态信息的结构。

习题

• 「SCOI2007」降雨量
• USACO07JAN 平衡的阵容 Balanced Lineup

这两题分别考察 RMQ 与其他信息结合、以及区间最值的综合运用，适合用来巩固 ST 表的模板与迁移能力。进一步地，可结合仓库的 RMQ 专题 对比 ST 表与其他 RMQ 解法（如线段树、分块、莫队）的适用场景，在「海量静态询问」与「动态修改」之间做出正确的结构选型。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki