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 等扩展信息时的复杂度分析帮助你在海量询问场景下写出可运行的完整代码。定义可重复贡献问题与 RMQST 表Sparse Table稀疏表是用于解决可重复贡献问题的数据结构。!!! note 什么是可重复贡献问题 可重复贡献问题是指对于运算 $\operatorname{opt}$满足 $x\operatorname{opt} xx$则对应的区间询问就是一个可重复贡献问题。例如最大值有 $\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,i2^j-1]$ 的最大值。显然 $f(i,0)a_i$即长度为 1 的区间最大值就是元素本身根据定义式第二维相当于倍增的时候「跳了 $2^j-1$ 步」。依据倍增思路写出状态转移方程$$ f(i,j)\max\bigl(f(i,j-1),,f(i2^{j-1},j-1)\bigr) $$即长度为 $2^j$ 的区间被拆成两个长度为 $2^{j-1}$ 的子区间左半区间 $[i,i2^{j-1}-1]$ 与右半区间 $[i2^{j-1},i2^j-1]$。查询两个区间覆盖一个询问对于每个询问 $[l,r]$把它分成两部分$[l,l2^s-1]$ 与 $[r-2^s1,r]$其中 $s\left\lfloor\log_2(r-l1)\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 vectorT; using VVT vectorVT; using func_type functionT(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 vectorT 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; vectorint a(n); for (int i : a) cin i; SparseTableint 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; }这个版本有三个值得注意的设计点运算可注入构造函数接受func_type _func参数默认为max。这意味着只需更换运算函数同一个类即可用于区间按位与、按位或、区间 GCD 等其他可重复贡献运算前提是该运算满足结合律与 $x\operatorname{opt}xx$。内建函数求对数lg2使用__builtin_clz在 $O(1)$ 内得到 $\lfloor\log_2 x\rfloor$且对 MSVC 编译器做了宏兼容处理映射为_lzcnt_u32体现了跨平台考虑。0-based 下标外部调用时query(x - 1, y - 1)与 1-based 的 C 版本形成对照。Python 实现见 sparse-table_1.pyimport sys input sys.stdin.readline class SparseTable: def __init__(self, arr: list, funcmin): 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工程化注意点输入输出优化此类题目输入输出数据量一般很大如 $m\le 2\times 10^6$建议开启输入输出优化。三种参考实现均使用了cin.tie(nullptr)-sync_with_stdio(false)或 Python 的sys.stdin.readline来加速 IO这一点在编写时不可省略。数组维度与缓存局部性预处理 ST 表时通常需要建立一个一维大小为 $\log n$、另一维大小为 $n$ 的数组。此时应优先让大小为 $\log n$ 的维度作为第一维即f[logN 1][N]而非f[N][logN 1]以提升缓存局部性。C 风格实现 sparse-table_1.cpp 正是按f[logN 1][N]声明的。对数计算每次用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开始对 $i3..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_{i1}^{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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考