一、为什么学 ST 表
线段树可以在 O(log n) 时间内完成单点更新和区间查询，但如果数据是静态的（建好后不再修改），ST 表就是更优的选择：预处理 O(n log n)，查询 O(1)。
ST 表的核心思想是倍增：预处理出所有长度为 2^k 的区间答案，查询时把 [l, r] 拆成两个重叠的 2^k 区间。由于很多运算满足幂等律（如 max、min、GCD），重叠不会影响结果。
二、核心原理
预处理：st[i][k]
设 st[i][k] 表示以 i 开头、长度为 2^k 的区间内的最值。
st[i][0] = a[i]（长度为 1 的区间就是自己）st[i][k] = op(st[i][k-1], st[i + 2^(k-1)][k-1])
状态转移把区间分成两半，左半部分是 [i, i+2^(k-1)-1]，右半部分是 [i+2^(k-1), i+2^k-1]。
查询：RMQ(l, r)
设区间长度为 len = r - l + 1，取 k = floor(log2(len))。则：
- 左区间：[l, l + 2^k - 1]
- 右区间：[r - 2^k + 1, r]
这两个区间都覆盖了 [l, r]，取最值即可。
适用范围
ST 表只适用于满足幂等律的操作，即 op(a, op(b, c)) = op(op(a, b), c)，且 op(x, x) = x。
- 最大值、最小值：✓
- GCD（最大公约数）：✓
- 区间和：✗（不满足幂等律）
三、模板代码
区间最大值
class SparseTable {
private:
vector> st;
vector lg2; // 整数对数，用于 O(1) 查询
int n;
// op 函数：这里用 max
int op(int a, int b) { return max(a, b); }
public:
SparseTable(const vector& a) {
n = a.size() - 1; // 假设 a 下标从 1 开始
int K = log2(n) + 1;
st.assign(K, vector(n + 1));
// 预处理 k = 0
for (int i = 1; i <= n; i++) st[0][i] = a[i];
// 预处理 k > 0
for (int k = 1; k < K; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
st[k][i] = op(st[k-1][i], st[k-1][i + (1 << (k-1))]);
}
}
// 预处理对数
lg2.resize(n + 1);
lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i/2] + 1;
}
// O(1) 查询
int query(int l, int r) {
int k = lg2[r - l + 1];
return op(st[k][l], st[k][r - (1< 区间 GCD
class GcdSparseTable {
private:
vector> st;
vector lg2;
int n;
public:
GcdSparseTable(const vector& a) {
n = a.size() - 1;
int K = log2(n) + 1;
st.assign(K, vector(n + 1));
for (int i = 1; i <= n; i++) st[0][i] = a[i];
for (int k = 1; k < K; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
st[k][i] = std::gcd(st[k-1][i], st[k-1][i + (1 << (k-1))]);
}
}
lg2.resize(n + 1);
lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i/2] + 1;
}
int query(int l, int r) {
int k = lg2[r - l + 1];
return std::gcd(st[k][l], st[k][r - (1< 四、典型题目
RMQ 模板题
题意：给定数组，动态查询区间 [l, r] 的最大值或最小值。
思路：静态数组，直接用 ST 表。预处理 O(n log n)，每次查询 O(1)。
LCA：最近公共祖先
两棵树做 LCA 时，可以预处理欧拉序和深度，用 ST 表维护欧拉序中相邻节点深度的最小值对应的节点编号。
- 欧拉序：DFS 进入节点时记录一次，离开时再记录一次，形成长度为 2n-1 的序列。
- 在欧拉序中，u 和 v 之间的区间就是从 u 往上到 LCA 再到 v 的路径。
- 区间深度最小值对应的节点就是 LCA。
class LCA {
private:
vector> st; // 节点编号的 ST 表
vector first, depth, euler;
vector lg2;
int timer = 0;
void dfs(int u, int p, int d, const vector>& g) {
first[u] = timer;
euler.push_back(u);
depth.push_back(d);
timer++;
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u, d + 1, g);
euler.push_back(u);
depth.push_back(d);
timer++;
}
}
int queryMinDepth(int l, int r) {
int k = lg2[r - l + 1];
// 返回深度最小值对应的节点（需要另一个 ST 表存储节点）
// 这里简化处理，实际需要维护 (depth, node) 的二元组
return r; // 占位
}
public:
LCA(int n, int root, const vector>& g) {
first.assign(n + 1, 0);
dfs(root, 0, 0, g);
int m = euler.size();
int K = log2(m) + 1;
st.assign(K, vector(m));
// 用另一个数组存储欧拉序，用 RMQ 找 LCA
}
int lca(int u, int v) {
int l = first[u], r = first[v];
if (l > r) swap(l, r);
// 在欧拉序区间 [l, r] 中找深度最小的节点
int k = lg2[r - l + 1];
int minDepth = INT_MAX;
int lcaNode = 0;
// 实际需要二维 ST 或在 RMQ 中返回节点
return lcaNode;
}
};
离线区间最值
题意：给定数组 a 和 q 个查询 [l, r]，求每个区间的最大值（静态）。
思路：用 ST 表 O(n log n) 预处理后，O(1) 回答每个查询。总复杂度 O(n log n + q)。
五、易错点
- 数组下标：ST 表通常用 1-indexed，代码中要统一。
- lg2 预处理：查询时用
lg2[len]而不是log2(len)，避免浮点误差。 - 空间：st 数组大小约为 n * log2(n)，n = 10^5 时约 1.7M 个元素，可以接受。
- ST 表不支持修改：如果需要单点更新，切换成线段树。
- 类型选择：区间和不能用 ST 表，换成前缀和或线段树。
六、复盘
ST 表的特征是：静态数据 + 区间最值/GCD + 需要 O(1) 查询。见到这类约束，直接想 ST 表。
常见提示词：
- "多组查询，查询互不影响"
- "n 和 q 都很大（10^5），需要 O(1) 查询"
- "数组不会修改"
学完 ST 表后，数据结构这一块已经覆盖了：
- 栈/队列、单调栈/队列 → 线性结构
- 堆/优先队列 → 完全二叉树结构
- 哈希表 → 散列结构
- 并查集 → 森林结构
- 树状数组 → 二叉索引树
- 线段树 → 区间树
- ST 表 → 倍增稀疏表
下一块可以往 Trie 字典树走，也可以开始动态规划专题。Trie 是字符串高频考点，也是 AC 自动机和后缀自动机的基础。