ST 表 (RMQ)NOIP

💡 核心思想

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

🎯 直觉理解

ST 表是"静态区间最值（RMQ）"的最强武器：预处理 $O(nlog n)$，之后每次查询 $O(1)$，不能修改（静态）。

核心是倍增预处理：$st[i][k]$ 表示从 i 开始、长度为 $2^k$ 的区间最值。$st[i][k]=max(st[i][k-1], st[i+2^{k-1}][k-1])$——两个半段拼成整段。

查询 $[l,r]$：取 $k$ 为区间长度的对数向下取整，区间最值 = max(从 l 开始的 $2^k$ 段, 以 r 结尾的 $2^k$ 段)——两段可能重叠，但最值重叠无所谓。"区间最值可重叠"是 ST 表 $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 
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<> l >> r;
        int k = lg[r - l + 1];
        cout << max(st[l][k], st[r-(1<