当前位置：首页 > news >正文

ST 表（Sparse Table）算法详解：原理、实现与应用

news 2026/7/22 23:25:23

1. 什么是 ST 表

ST 表（Sparse Table，稀疏表）是一种用于解决静态区间最值查询（RMQ）问题的数据结构。它可以在 O(n log n) 的预处理时间后，以 O(1) 的时间复杂度回答任意区间 [l, r] 的最小值、最大值、最大公约数等可重复贡献问题的查询。

2. 核心思想与原理

ST 表的核心思想是倍增和动态规划。对于长度为 n 的数组 arr，我们预处理一个二维数组 st[i][j]，表示从位置 i 开始，长度为 2^j 的区间（即区间 [i, i + 2^j - 1]）的查询结果（如最大值）。

状态转移方程为：

st[i][j] = f(st[i][j-1], st[i + 2^(j-1)][j-1])

其中 f 是满足可重复贡献性质的二元运算，如 max、min、gcd 等。

对于查询区间 [l, r]，我们找到最大的 k 使得 2^k ≤ (r - l + 1)，然后通过两个长度为 2^k 的区间覆盖 [l, r]：

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

由于运算 f 满足可重复贡献性质，即使这两个区间有重叠，最终结果也是正确的。

3. 算法实现（C++）

3.1 预处理

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int LOG = 20; // log2(MAXN) int st[MAXN][LOG]; int log2_pre[MAXN]; // 预处理 log2 值 void preprocess(vector<int>& arr) { int n = arr.size(); // 预处理 log2 值 log2_pre[1] = 0; for (int i = 2; i <= n; i++) { log2_pre[i] = log2_pre[i / 2] + 1; } // 初始化：长度为 1 的区间 for (int i = 0; i < n; i++) { st[i][0] = arr[i]; } // 动态规划构建 ST 表 for (int j = 1; j < LOG; 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]); } } }

3.2 查询操作

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

4. 时间复杂度分析

预处理：O(n log n)
单次查询：O(1)
空间复杂度：O(n log n)

与线段树（查询 O(log n)）相比，ST 表在查询速度上更有优势，但不支持修改操作，适用于静态数据场景。

5. 应用场景

静态 RMQ 问题：数组固定不变，频繁查询区间最值
LCA（最近公共祖先）：结合欧拉序和 ST 表可以在 O(1) 时间内回答 LCA 查询
区间 GCD 查询：同样满足可重复贡献性质
二维 RMQ：扩展到二维数组的静态区间查询
竞赛编程：常用于需要快速区间查询的题目

6. 优缺点总结

优点	缺点
查询速度极快（O(1)）	不支持修改操作
代码实现相对简单	空间复杂度较高（O(n log n)）
适用于静态数据场景	只能处理可重复贡献问题
可扩展到多维	预处理时间较长

7. 实战例题

7.1 洛谷 P3865 【模板】ST 表

题目描述：给定一个长度为 n 的数列，和 m 次询问，每次询问区间 [l, r] 的最大值。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int LOG = 17; int st[MAXN][LOG]; int log2_pre[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } // 预处理 log2 log2_pre[1] = 0; for (int i = 2; i <= n; i++) { log2_pre[i] = log2_pre[i / 2] + 1; } // 构建 ST 表 for (int i = 0; i < n; i++) { st[i][0] = arr[i]; } for (int j = 1; j < LOG; 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]); } } // 处理查询 while (m--) { int l, r; cin >> l >> r; l--; r--; // 转换为 0-based int k = log2_pre[r - l + 1]; cout << max(st[l][k], st[r - (1 << k) + 1][k]) << "\n"; } return 0; }