快速查询区间最值：用ST表当你的“身高答案手册”

你有没有在排队时被问过：“从第3个人到第8个人，谁最矮？”如果只问一次，挨个看看就行；但如果问几十次、几百次，每次还要重新数一遍，是不是特别慢？ST表就像一本提前算好的“身高答案手册”，翻开就能直接告诉答案，而且每次回答只用一瞬间。

ST表（Sparse Table，稀疏表）是一种数据结果，专门用来快速回答静态数组任意区间的最小值或最大值问题。它只适合数据固定不变的场景（比如班级同学的身高不会突然改变），但查询速度极快——每次只需 O(1) 的时间，就像查字典一样。

下面我们分步来认识它。

1. ST表的“空间换时间”思路

普通方法：每次询问一个区间 [l, r]，就遍历从 l 到 r 的所有元素，找最小（或最大）值。假设有 n 个元素，m 次询问，总时间就是 O(n×m)。当 n 和 m 都很大时，比如 n=100000，m=100000，计算量会爆炸。

ST表的策略：把数组划分成许多长度为 2 的幂的小区间，提前把所有小区间的最值都算好存起来。比如，存好从位置 i 开始，长度为 2^0=1、2^1=2、2^2=4……的最值。

• 预处理时间：O(n log n)
• 存储空间：O(n log n)
• 每次查询时间：O(1)

这就像你提前统计了每段连续位置的最矮身高，列了一个表。问的时候，只需要查表合并两个区间就能得到答案。

2. 核心思想：倍增 + 动态规划

2.1 表格定义

我们准备一个二维数组 st[i][j]，表示从数组的下标 i 开始，长度为 2^j 的区间的最小值。

• 当 j=0 时，区间长度就是 1，所以 st[i][0] = arr[i]（自己就是最值）。
• 当 j>0 时，长度为 2^j 的区间可以拆成两个长度为 2^(j-1) 的区间：
  前半段：[i, i+2^(j-1)-1] → 最小值是 st[i][j-1]
  后半段：[i+2^(j-1), i+2^j-1] → 最小值是 st[i + 2^(j-1)][j-1]

于是得到递推公式：

st[i][j] = min( st[i][j-1], st[i + (1<<(j-1))][j-1] )

这里的 1<<(j-1) 就是 2^(j-1)，用位运算更快。

2.2 生活中的例子

假设你班上有8位同学，身高（厘米）分别是：150, 140, 160, 130, 170, 145, 155, 165。用 arr 表示：
下标：0 1 2 3 4 5 6 7
身高：150,140,160,130,170,145,155,165

我们想提前算好所有长度为1、2、4、8的区间的最矮身高。

• 长度为1（j=0）：st[i][0] 就是 arr[i] 本身。
• 长度为2（j=1）：例如 [0,1] 的最矮是 min(150,140)=140；[2,3] 最矮是 min(160,130)=130；……
  st[0][1] = min(st[0][0], st[1][0]) = 140
• 长度为4（j=2）：例如 [0,3] 的最矮 = min( 前2个的最矮140, 后2个的最矮130 ) = 130
  st[0][2] = min(st[0][1], st[2][1]) = min(140,130)=130
• 长度为8（j=3）：[0,7] 最矮 = min( [0,3]最矮130, [4,7]最矮145 ) = 130

这样，任意一个长度为2的幂的区间的最小值，我们都提前算好了。

3. 如何用ST表快速回答任意区间？

3.1 查询方法

假如现在要查询区间 [l, r] 的最小值，区间长度 len = r - l + 1。
我们找到最大的 k，使得 2^k ≤ len（也就是 k = floor(log2(len))）。

然后，我们用 两个长度为 2^k 的区间 来覆盖整个 [l, r]：

• 第一个区间从 l 开始，长度为 2^k → st[l][k]
• 第二个区间从 r - 2^k + 1 开始，长度为 2^k → st[r - (1<<k) + 1][k]

这两个区间可能有重叠，但它们的并集一定覆盖了整个 [l, r]（因为 2^k ≥ len/2，两个区间加起来长度≥len，且一个靠左一个靠右）。最小值就是这两个区间的最小值中的较小者。

答案 = min( st[l][k], st[r - (1<<k) + 1][k] )

3.2 直观理解

想象你有一把尺子，长度是 2^k。你不能直接量出任意长度，但可以用两把相同的尺子覆盖任意区间：一把从左边开始，一把从右边开始，中间可能重叠，但覆盖的区域一定包含你要的全部位置。

比如区间长度 len=5，最大的 2^k=4（k=2）。

• 第一把尺覆盖 [l, l+3]
• 第二把尺覆盖 [r-3, r]
  这两把尺加起来覆盖了 [l, r] 中的所有位置，不会遗漏。

3.3 查询例子

用上面的身高数组，查询区间 [2,5]（下标从0开始，对应身高160,130,170,145）。
len = 5-2+1=4。log2(4)=2，所以 k=2。
第一段：从下标2开始，长度4 → st[2][2] 是什么？我们需要提前算好。
第二段：从下标 5-4+1=2 开始，长度4 → 又是 st[2][2]（因为刚好对齐）。所以答案就是 st[2][2]。
实际 st[2][2] 是区间 [2,5] 的最小值，提前算出来应该是 130（因为130在位置3）。查询结果是130。

再查区间 [1,6]（长度6，k=2，因为2^2=4 ≤6，2^3=8>6）：
第一段：st[1][2]（区间[1,4]的最小值：140,160,130,170 → 130）
第二段：st[6-4+1=3][2]（区间[3,6]的最小值：130,170,145,155 → 130）
答案 min(130,130)=130。

4. 完整代码与注释

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAXN = 100005;    // 数组最大长度
const int LOGN = 17;        // log2(100005) < 17，2^17=131072够用
int st[MAXN][LOGN];         // st[i][j] 表示从i起始、长度为2^j的区间最小值

int main() {
    // 示例数据：8位同学的身高
    vector<int> arr = {150, 140, 160, 130, 170, 145, 155, 165};
    int n = arr.size();      // 数组长度

    // 初始化：长度为1的区间
    for (int i = 0; i < n; i++) {
        st[i][0] = arr[i];   // 每个位置自己就是最小值
    }

    // 动态规划预处理：j从1开始，长度2^j不能超过n
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            // 前半段：st[i][j-1]  后半段：st[i+(1<<(j-1))][j-1]
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }

    // 查询区间 [2,5]（下标从0开始，对应身高160,130,170,145）
    int l = 2, r = 5;
    int len = r - l + 1;        // 区间长度6
    int k = log2(len);          // k = floor(log2(len))
    int ans = min(st[l][k], st[r - (1 << k) + 1][k]);
    cout << "区间[" << l << "," << r << "]的最小值是：" << ans << endl;

    // 也可以让用户输入查询：
    // cout << "输入l和r（下标从0开始）：";
    // cin >> l >> r;
    // len = r - l + 1;
    // k = log2(len);
    // ans = min(st[l][k], st[r - (1<<k) + 1][k]);
    // cout << ans << endl;

    return 0;
}

代码中：

• 1<<j 是 2 的 j 次方
• i + (1<<j) - 1 < n 确保区间不越界
• log2 函数来自 <cmath>，返回 double，自动向下取整（因为赋值给 int 时截断小数）

5. 新手容易犯的错误

❌ 错误1：下标忘记偏移

查询时第二个区间起始位置是 r - (1<<k) + 1，很容易写成 r - (1<<k) 或 r - (1<<k) + 0，导致取到的区间不对。

正确做法： 先算出长度，再确认第二个区间覆盖到 r。例如当前区间 [l,r] 长度 len，2^k≤len，那么从左边开始覆盖到 l+2^k-1，右边需要从 r-2^k+1 开始覆盖到 r。

❌ 错误2：log2 使用不正确

log2 返回 double，如果直接赋值给 int，系统自动截断小数部分（向下取整）。但如果有浮点误差（比如 log2(8) 可能返回 2.9999999），截断后得到 2 而不是 3。解决方案：

• 使用 int k = __lg(len) （GCC 内置函数，返回整数）
• 或手动计算：int k = 31 - __builtin_clz(len); （GCC 的计数前导零函数）

❌ 错误3：预处理时 j 的循环范围

for (int j = 1; (1<<j) <= n; j++) 是正确的，因为长度为 2^j 的区间最大不能超过 n。如果写成 j < LOGN 可能浪费计算，但不会出错（超出的 j 对应的 i 循环条件会阻止进入）。

❌ 错误4：误用 ST表 处理动态修改的数组

ST表预处理后，一旦数组元素发生变化（比如某位同学突然长高了），所有涉及该位置的 st 值都可能失效。如果数据经常变化，应该使用线段树或树状数组，而不是 ST表。

6. 完整示例：互动式查询

下面给出一个更完整的示例程序，让用户输入数组和查询，直接输出结果。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int main() {
    int n;  // 数组大小
    cout << "请输入数组长度: ";
    cin >> n;
    vector<int> arr(n); // 存储原始数据
    cout << "请输入 " << n << " 个整数: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 计算最大log值
    int LOG = log2(n) + 1;
    vector<vector<int>> st(n, vector<int>(LOG)); // 二维ST表

    // 初始化
    for (int i = 0; i < n; i++) {
        st[i][0] = arr[i];
    }

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

    // 查询
    int q; // 询问次数
    cout << "请输入询问次数: ";
    cin >> q;
    while (q--) {
        int l, r;
        cout << "输入l和r（下标从0开始）: ";
        cin >> l >> r;
        int len = r - l + 1;
        int k = log2(len);
        int ans = min(st[l][k], st[r - (1 << k) + 1][k]);
        cout << "区间[" << l << "," << r << "]的最小值为: " << ans << endl;
    }

    return 0;
}

运行示例：

请输入数组长度: 8
请输入 8 个整数: 150 140 160 130 170 145 155 165
请输入询问次数: 2
输入l和r（下标从0开始）: 2 5
区间[2,5]的最小值为: 130
输入l和r（下标从0开始）: 1 6
区间[1,6]的最小值为: 130

7. 相关指引：ST表还能做什么？

• 区间最大值：只需把 min 改成 max，其他完全一样。
• 区间最大公约数、区间按位与/或：只要运算满足可重复贡献（即两个重叠区间合起来覆盖整个区间，结果不变），ST表都适用。
• 求最近公共祖先（LCA）：将树转化为欧拉序列后，可以用ST表快速回答深度最小的点（区间最小值）。

ST表的局限性是不能处理动态修改，如果需要修改，请学习线段树或树状数组。对于数据不动的场景，ST表就是最快的选择，就像拥有了一本万能答案手册。