ST 表 (Sparse Table) - 数据结构

什么是 ST 表？

ST 表（Sparse Table，稀疏表）是一种解决 区间最值查询 (RMQ, Range Minimum/Maximum Query) 问题的经典静态数据结构：

预处理时间复杂度：$O(N \log N)$（使用动态规划进行倍增计算）
单次查询时间复杂度：极其高效的 $O(1)$

倍增状态与递推关系

设 $f[i][j]$ 表示原数组中区间 $[i, i + 2^j - 1]$ 的最大值。其区间长度为 $2^j$。

长度为 $2^j$ 的区间可等分为两个长度为 $2^{j-1}$ 的子区间：$[i, i + 2^{j-1} - 1]$ 和 $[i + 2^{j-1}, i + 2^j - 1]$。

状态转移方程：$$ f[i][j] = \max(f[i][j-1],\, f[i + 2^{j-1}][j-1]) $$

数组大小 $N$：

点击"单步建表"或"自动建表"来观察 DP 表 $f[i][j]$ 的倍增填表过程。

原数组 A

DP 状态表 $f[i][j]$ (各单元格值表示所覆区间的最大值)

C++ 核心代码对照

ST 表 (区间最大值) C++ 标准实现

// 预处理建表
void initST(int n, const vector<int>& a) {
    // f[i][j] 表示区间 [i, i + 2^j - 1] 的最大值
    for (int i = 0; i < n; i++) {
        f[i][0] = a[i];  // 长度为 2^0 = 1 的区间最大值就是自身
    }
    
    // 倍增递推填充
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// O(1) 查询区间 [L, R] 的最大值
int query(int L, int R) {
    int len = R - L + 1;
    int k = log2(len); // 计算最大重叠区间步长，即 2^k <= len
    return max(f[L][k], f[R - (1 << k) + 1][k]);
}