ST表

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)$：