ST 表

概念讲解

什么是 ST 表？

ST 表（Sparse Table）用于静态区间最值查询，预处理 O(nlog⁡n)O(n \log n)，查询 O(1)O(1)。

核心思想

利用倍增思想，st[i][j]st[i][j] 表示从 i 开始长度为 2j2^j 的区间的最值。

实现

123456789101112131415161718const int N = 100005;
const int LOG = 20;
int st[N][LOG];
int a[N], n;

void build() {
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    for (int j = 1; j < LOG; 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]);
        }
    }
}

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

局限性

  • 只能查询，不能修改
  • 只适用于可重复贡献问题（如 max, min, gcd）

考点分析

初赛考查方式

  1. 程序阅读： ST 表操作
  2. 编程题： RMQ 问题

常见考点

  • ST 表构建
  • O(1) 查询
  • 局限性

练习题

  1. ST 表的查询时间复杂度是多少？
查看答案

O(1)O(1)

1234int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
  1. ST 表的局限性是什么？
查看答案

ST 表的局限性：

  1. 只能查询，不能修改：数组是静态的
  2. 只适用于可重复贡献问题：如 max, min, gcd, AND, OR
  3. 不支持区间修改：无法进行加、减等操作
  1. ST 表和线段树的区别？
查看答案
特性 ST 表 线段树
预处理 O(nlog⁡n)O(n \log n) O(n)O(n)
查询 O(1)O(1) O(log⁡n)O(\log n)
修改 不支持 支持
空间 O(nlog⁡n)O(n \log n) O(4n)O(4n)

ST 表适合静态查询，线段树适合动态修改。

易错点

⚠️ 注意：

  1. ST 表是静态的
  2. 查询 O(1) 是优势
  3. 只适用于可重复贡献问题
  4. 要预处理 log2