ST表

题单类型：官方题单

创建人：

ACGO官方

题数：20题

收藏题单

完成度：0/20

ST 表

1. ST 表模板：解决 RMQ（区间最值）问题

核心

基于倍增的思想，预处理ST表之后，可以快速查询静态区间的区间最值，也就是解决静态RMQ问题
查询 $[L,R]$ 时，令 $k=\lfloor \log_2(R-L+1)\rfloor$ ，答案来自两个重叠块：

$\text{ans} = \text{op}\big(\text{st}[k][L],\ \text{st}[k][R-2^k+1]\big)$
预处理复杂度 $O(nlog n)$ ，单次查询 $O(1)$ 。
st表在进行区间最值查询操作的情况下，时间复杂度比其他数据结构更为优秀

//ST表求最值模板
int n, m;
int a[N];
int st[N][20];  // st[i][j] 表示从 i 开始长度为 2^j 的区间的最小值
int lg[N];      // 预处理 log2

// 预处理 log2 和 ST 表
void init() {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;

    for (int i = 1; i <= n; i++) st[i][0] = a[i];

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// 查询区间 [l, r] 的最小值
int query(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

2. ST 表解决“可重复贡献”问题

定义
- 可重复贡献：运算满足 $f(x,x)=x$ ，且区间可以被重叠覆盖而不影响答案。
- 常见可重复贡献运算：
  - $\min,\ \max,\ \gcd,\ \text{bitwise AND/OR}$
- 不满足的运算：
  - $\text{sum},\ \text{xor},\ \text{product}$
应用
- 区间最值（RMQ）
- 区间 $\gcd$
- 区间 AND / OR（常用于阈值判定）

3. ST 表优化与应用

3.1 静态 RMQ 替代

在需要频繁查询区间最值、最小值或 $\gcd$ 时，用 ST 表将复杂度从 $O(\log n)$ 降到 $O(1)$ 。

3.2 倍增 / 二分找边界

常见套路：

最长子段最小值 $\ge x$
区间 $\gcd \ge g$

在循环中用 ST 表判定区间条件，结合二分或倍增求边界。

3.3 ST 表优化动态规划

当上一层 DP 结果固定后（静态数组），下一层转移需要多次区间最值查询时：

$dp_t[i] = \min_{j\in[L(i),R(i)]}\{dp_{t-1}[j] + cost(j,i)\}$

若 cost 与 $j$ 无关，可用 ST 表在 $O(1)$ 求 RMQ，整体复杂度显著降低。

3.4 st表求LCA（欧拉序 + RMQ）

对树进行欧拉序遍历，记录每次访问节点的深度。
$LCA(u,v) = \text{欧拉序上 } [pos(u),pos(v)]$ 的最小深度点。
ST 表在深度数组上 RMQ 查询 → $O(1)$ 求 LCA，比起倍增求LCA，st表求解方法在查询操作上更快速。

4. 在线维护ST表

核心

st表是一种静态的数据结构，不支持在线修改，但是有一种情况例外：

当新插入的元素只会从数组的一端插入的情况下，可以为该点以O(logn)的复杂度单独维护对应的st表。

5. 二维 ST 表

预处理思路

预处理所有大小为 $2^{kx}\times 2^{ky}$ 的子矩形：

$st[kx][ky][i][j] = \text{矩形 } [i, i+2^{kx}-1] \times [j, j+2^{ky}-1] \text{ 的最小值}$
查询矩形 $(x_1,y_1,x_2,y_2)$ ：

$\min(A,B,C,D)$

四个重叠块分别覆盖矩形的四个角。

【后置衔接知识点】
1、动态规划的优化

【思维导图】

【题目知识点分类】

ST表