ST 表 (RMQ)CSP-S

💡 核心思想

ST 表（Sparse Table）用于静态区间最值查询（RMQ）。预处理 $O(n \log n)$，查询 $O(1)$。不支持修改。核心是倍增思想：$st[i][j]$ 表示从位置 $i$ 开始、长度为 $2^j$ 的区间的最值。

🎯 直觉理解

ST 表就像"预计算好的统计报表"。你对每种长度的区间都预先算好最值，查询时只需要查两张表取最大值。因为"两个可能重叠的区间取最大值"不影响结果（max 操作幂等），所以可以 $O(1)$ 查询。

📝 算法流程

1. 预处理：$st[i][0] = a[i]$，$st[i][j] = \max(st[i][j-1], st[i+2^{j-1}][j-1])$
2. 查询：找最大的 $k$ 使得 $2^k \le r-l+1$，取 $\max(st[l][k], st[r-2^k+1][k])$
3. 不支持修改

$$st[i][j] = \max(st[i][j-1],\ st[i + 2^{j-1}][j-1])$$

$$\text{查询} [l,r]: \max(st[l][k],\ st[r-2^k+1][k]),\ k = \lfloor \log_2(r-l+1) \rfloor$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int st[100005][20], lg[100005];
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> st[i][0];
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 1; 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;
        int k = lg[r - l + 1];
        cout << max(st[l][k], st[r-(1<<k)+1][k]) << "\n";
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目