CC++ & Algorithm

ST表（Sparse Table）与RMQ

极难4
语言版本：通用
概述：用预处理和倍增思想，在O(1)时间内回答区间最大值/最小值查询，就像提前准备好所有可能长度的尺子。

又快又准的区间最值查询：ST表（Sparse Table）入门

这玩意儿是干啥的？

你是不是经常遇到这样的问题：给你一个长长的数字列表，然后有人不停地问“从第 l 个到第 r 个，这里面最大的数是多少？”（或者最小的）。比如老师统计全班同学的成绩，想知道学号 5 到 15 中谁考得最高；或者你在玩猜数字游戏，要快速知道某一段数据里的最大值。如果每次都要从头到尾看一遍，数据多了就慢得像爬虫。

ST表（Sparse Table，稀疏表） 就是专门用来解决这类问题的“超级尺子”。它提前做好一张魔法表格，把每种可能长度的区间最值都算出来存好。以后无论问哪个区间，只要从表格里找出两段覆盖它的“大块”，比一比就能瞬间得到答案。它的特点是：

  • 预处理时间：O(n log n)（n是数据个数，log n通常很小，比如n=1万时log n≈14）
  • 每次查询时间：O(1) —— 常数时间，快得飞起！
  • 适用场景：数据固定不变（不增不减不改），只查询区间最值（最大值、最小值、GCD、按位与……但不能求区间和）。

可以把ST表想象成一本“区间答案速查手册”。你在手册里翻到对应的页，直接抄答案就行，不用再算。

生活中的例子：班级成绩查询

还记得开头那个老师问“学号5到学号15中谁成绩最高”的问题吗？我们来细想一下怎么用ST表的思想解决。

假设全班有50个同学，每个人的成绩存成一个数组 scores[1..50]。老师可能随时问任意的区间。如果每次我们都把区间里的同学一个个看，最坏情况下要比较50次，问100次就是5000次比较，有点累。

于是我们提前准备一张“神奇成绩表”。这张表的每一行代表长度为2的幂的区间：

  • 第0行：每个同学自己的成绩（长度为1 = 2⁰）
  • 第1行：每相邻两个同学中较高的成绩（长度为2 = 2¹）
  • 第2行：每连续四个同学中较高的成绩（长度为4 = 2²）
  • 第3行：每连续八个同学中较高的成绩（长度为8 = 2³）
  • ……

当老师问区间 [5, 15] 时，长度是 11。我们找到小于等于11的最大的2的幂，那就是8（2³=8）。然后用两个长度为8的区间完全盖住 [5,15]：

  • 第一个区间：从5开始，覆盖5~12
  • 第二个区间：从8开始，覆盖8~15（因为15-8+1=8）

这两个区间覆盖了原区间的所有元素（有重叠也没关系），取出各自的最大值，再比较，就得出了答案。

这样，无论区间多大，我们只需要查两次表格，比一次大小，搞定！这就是ST表的魔法。

数据结构原理和核心思想（加细版）

1. 预处理阶段 – 建表

我们有一个数组 a[1..n]（下标从1开始，方便理解）。定义 st[i][j] 表示：以 i 为起点、长度为 2^j 的区间内的最大值。

  • 当 j = 0 时，区间长度是 1，只有 a[i] 自己，所以 st[i][0] = a[i]。
  • 当 j > 0 时，长度为 2^j 的区间可以分成两个长度为 2^(j-1) 的区间： 
    区间 [i, i+2^j-1] = [i, i+2^(j-1)-1] ∪ [i+2^(j-1), i+2^j-1]
    左边区间的最大值是 st[i][j-1]，右边区间的是 st[i + 2^(j-1)][j-1]。整个区间的最大值就是这两者的最大值： 
    st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])

举个例子：假设数组 a = [3, 1, 2, 5, 4, 6, 0, 7]（n=8，下标从1开始）。

先初始化 j=0：

st[1][0]=3, st[2][0]=1, st[3][0]=2, st[4][0]=5, st[5][0]=4, st[6][0]=6, st[7][0]=0, st[8][0]=7

计算 j=1（长度为2）：

  • st[1][1] = max(st[1][0], st[2][0]) = max(3,1)=3
  • st[2][1] = max(st[2][0], st[3][0]) = max(1,2)=2
  • st[3][1] = max(st[3][0], st[4][0]) = max(2,5)=5
  • st[4][1] = max(st[4][0], st[5][0]) = max(5,4)=5
  • st[5][1] = max(st[5][0], st[6][0]) = max(4,6)=6
  • st[6][1] = max(st[6][0], st[7][0]) = max(6,0)=6
  • st[7][1] = max(st[7][0], st[8][0]) = max(0,7)=7

计算 j=2（长度为4）：

  • st[1][2] = max(st[1][1], st[3][1]) = max(3,5)=5
  • st[2][2] = max(st[2][1], st[4][1]) = max(2,5)=5
  • st[3][2] = max(st[3][1], st[5][1]) = max(5,6)=6
  • st[4][2] = max(st[4][1], st[6][1]) = max(5,6)=6
  • st[5][2] = max(st[5][1], st[7][1]) = max(6,7)=7

j=3（长度为8）：

  • st[1][3] = max(st[1][2], st[5][2]) = max(5,7)=7

整理成表格（行表示 j，列表示 i，只展示有值的部分）：

j=0: | 3 | 1 | 2 | 5 | 4 | 6 | 0 | 7 |
j=1: | 3 | 2 | 5 | 5 | 6 | 6 | 7 |   |
j=2: | 5 | 5 | 6 | 6 | 7 |   |   |   |
j=3: | 7 |   |   |   |   |   |   |   |

2. 查询阶段 – 快速取答案

要查询区间 [l, r]，长度 len = r - l + 1。我们找到最大的 k 使得 2^k ≤ len，即 k = floor(log2(len))。然后取两个长度为 2^k 的区间：

  • 第一个：从 l 开始，覆盖 [l, l+2^k-1]
  • 第二个：从 r-2^k+1 开始，覆盖 [r-2^k+1, r]

这两个区间可能有重叠，但没关系，因为我们要的是最大值，重叠部分的重复计算不会影响结果（求最大值是“可重复贡献”的）。整个区间的最大值就是这两个区间最大值的较大者。

举例：查询区间 [2,6]（下标从1开始，实际元素位置2-6是 1,2,5,4,6）。

  • len = 6-2+1 = 5
  • 最大的 k 使得 2^k ≤ 5：2²=4，2³=8>5，所以 k=2
  • 区间1：从 l=2 开始，长度4 → [2,5] → 查 st[2][2] = 5（对应元素1,2,5,4的最大值5）
  • 区间2：从 r-2^k+1 = 6-4+1=3 开始 → [3,6] → 查 st[3][2] = 6（对应2,5,4,6的最大值6）
  • 答案 = max(5,6) = 6，正确！

为什么可以用两个重叠区间覆盖？因为我们要的是最大值，重叠部分被算了两次，但取 max 时重复不会出错。这要求运算必须是“可重复贡献”的（比如 max, min, gcd, 按位与、按位或）。而区间和就不行，因为重叠部分会重复加。

3. 为什么叫 Sparse Table？

“Sparse”是“稀疏”的意思。因为表格只存了长度为2的幂的区间，其他长度不存，所以表格是稀疏的（有很多空白）。但正是这种稀疏性，让我们能用 O(n log n) 的空间存储所有必要的信息，并且查询时只需两个片段。

新手容易犯的错误

  1. 下标混淆：C++代码里下标从1开始，Python代码里下标从0开始。如果混用，区间 [l, r] 的含义会不同，导致越界或错误结果。建议统一用一种习惯，并写清楚注释。

  2. log2 取整问题：在C++中 log2(r-l+1) 返回 double，赋值给 int k 时会自动截断小数部分。理论上没问题，但有些编译器可能因为浮点误差导致结果偏小（比如本应是 2.0 却变成 1.9999999），截断后变成 1。稳妥的做法是用位移或预计算对数表（像Python代码那样）。例如：

    int k = 0;
while ((1 << (k+1)) <= len) k++;   // 手动求最大幂

  3. 数组大小不够：ST表需要 n * (log2(n)+1) 的大小。经常有人忘记开大 LOG 的值。比如 n=100000，log2(100000)≈17，所以需要至少17列（从0到16）。一般取 17 或 20 作为保险。

  4. 用ST表求区间和：这是错误的！因为重叠部分会重复计算。如果想快速求和，应该用前缀和或者线段树。

  5. 修改数据后还用ST表：ST表只适合静态数据。如果数组里的值会变，需要支持修改操作，那么请用线段树或树状数组。

完整代码实现（带详细注释）

C++ 版（下标从1开始）

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

const int MAXN = 100005;    // 最大数组长度
const int LOG = 17;         // 2^17 = 131072 > 100000，足够用

int st[MAXN][LOG];  // st[i][j] 表示从i开始长度为2^j的区间最大值
int a[MAXN];        // 原始数组
int n;              // 数组长度

// 预处理：构建st表
void build() {
    // 第0层：长度为1的区间
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
    }
    // 动态规划，j从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]);
        }
    }
}

// 查询区间[l, r]的最大值
int query(int l, int r) {
    int len = r - l + 1;            // 区间长度
    // 方法1: 用log2函数（需#include <cmath>）
    int k = log2(len);              // 向下取整
    // 方法2（更安全的手动求法）：
    // int k = 0;
    // while ((1 << (k+1)) <= len) k++;
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    cout << "请输入数组长度n: ";
    cin >> n;
    cout << "请输入" << n << "个整数: ";
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build();

    int q;
    cout << "请输入查询次数: ";
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << "区间[" << l << "," << r << "]的最大值为: " << query(l, r) << endl;
    }
    return 0;
}

Python 版（下标从0开始，含对数预计算）

import math

def build_sparse_table(arr):
    """
    构建st表
    arr: list，原始数组（下标从0开始）
    返回: (st, log)  其中st是二维列表，log是预计算的对数表
    """
    n = len(arr)
    # 预计算log2(1) ~ log2(n)
    log = [0] * (n + 1)
    for i in range(2, n + 1):
        log[i] = log[i // 2] + 1   # 递推公式：log2(i) = log2(i//2) + 1

    K = log[n] + 1   # 最大层数
    # 初始化st表，大小 n x K，全部填0
    st = [[0] * K for _ in range(n)]

    # 第0层：长度1
    for i in range(n):
        st[i][0] = arr[i]

    # 动态规划
    j = 1
    while (1 << j) <= n:   # 2^j <= n
        i = 0
        while i + (1 << j) - 1 < n:   # 保证起始位置不越界
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1])
            i += 1
        j += 1

    return st, log

def query(l, r, st, log):
    """
    查询区间 [l, r] 的最大值（0-indexed）
    """
    k = log[r - l + 1]    # 直接查表，O(1)
    return max(st[l][k], st[r - (1 << k) + 1][k])

if __name__ == "__main__":
    n = int(input("请输入数组长度: "))
    arr = list(map(int, input("请输入数组元素: ").split()))
    
    st, log = build_sparse_table(arr)
    
    q = int(input("请输入查询次数: "))
    for _ in range(q):
        l, r = map(int, input("请输入查询区间[l r] (0-indexed): ").split())
        result = query(l, r, st, log)
        print(f"区间[{l},{r}]的最大值为: {result}")

更多应用：不止最大最小值

ST表的核心是可重复贡献运算。除了 max 和 min，还可以用于：

  • 最大公约数（GCD）：st[i][j] = gcd(st[i][j-1], st[i+2^(j-1)][j-1])
  • 按位与（&）：st[i][j] = st[i][j-1] & st[i+2^(j-1)][j-1]
  • 按位或（|）：类似

但不能用于求和、求平均数等，因为重叠部分会重复计算。

相关知识点拓展

  • 线段树：也支持区间查询，但还能修改值（更新操作）。不过线段树的查询时间是 O(log n)，比 ST 表慢一点点。如果你的数据是静态的（只查不改），ST表是更好的选择。
  • 树状数组：支持单点修改+区间求和，不能直接求最值（需要变种）。
  • 倍增法：ST表用的就是倍增思想，和求LCA（最近公共祖先）的倍增法很像，思路可以互相借鉴。
  • RMQ的其他解法：分块、笛卡尔树 + LCA 等，但 ST 表实现最简单、查询最快。

总结

ST表是解决静态区间最值查询的利器：用 O(n log n) 的预处理和 O(1) 的查询，让你在大量询问面前游刃有余。想象一下，如果老师给你一张全班同学的成绩表，然后连续问 1000 个区间最大值，你用ST表的话，眨眼间就能全部答完。下次遇到这类问题，别忘了拿出你的“魔法表格”哦！

例题精讲

1单选题

使用ST表（Sparse Table）进行RMQ（区间最值查询）时，预处理的时间复杂度是？

AO(n)
BO(n log n)
CO(n^2)
DO(log n)
2判断题

ST表（Sparse Table）支持高效的在线修改操作，即可以在O(log n)时间内更新一个元素并维护区间最值查询。

3填空题
以下函数用ST表查询区间 [l, r] 的最大值，请补全代码（数组下标从0开始，log2预处理完成）：

int query(int l, int r) {
    int k = (int)(log2(r - l + 1));
    return max(st[l][k], st[___][k]);
}
4单选题

关于ST表（Sparse Table）的适用场景，下列说法正确的是？

A可以高效处理区间和查询
B可以高效处理区间最大值查询
C可以高效处理区间中位数查询
D可以高效处理区间众数查询
5填空题
以下代码用于构建ST表，数组a[0..n-1]存储原始数据，st[i][k]表示起始位置i、长度为2^k的区间最大值。请补全预处理部分的合并逻辑（k从1开始，i从0到n-(1<<k)）：

for (int k = 1; (1 << k) <= n; k++) {
    for (int i = 0; i + (1 << k) - 1 < n; i++) {
        st[i][k] = max(st[i][k-1], st[___][k-1]);
    }
}