ST 表

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。

引导

问题：给定 $n$ 个数，有 $m$ 个询问，对于每个询问，你需要回答区间 $[l,\;r]$ 中的最大值。

暴力做法就是在查询时枚举这个区间，时间复杂度为：

O(nm)

显然这种做法并不明智，虽然代码简短。

那么我们考虑打表，枚举出每个区间，直接得出每个区间的最大值，在查询时直接输出即可。然而我们知道一个数组至少有

\frac{n(n + 1)}{2}

个子串，枚举过程中是

O(n^2)

的时间复杂度，还是会炸。

但是啊，每个区间会有重叠，比如：

那么这里的时间我们就浪费了，因为在

[L_1,\;\;R_1]

子串已经计算过了，所以

[L_2,\;\;R_2]

就不需要重新计算，所以时间复杂度会降低，那我们该怎么做呢？

正文（什么是ST表）

字面意义稀疏表，它的时间/空间是

O(n\,log\,n)

，主要是因为需要查询的子串是由两个已经计算好的子串重新 opt得来的，所以比

n^2

快。ST表运用了倍增的思路，倍增法成功的缩短了预处理多余的空间，主要过程为：

(max=max+max，其中的 + 为 opt)

其中，

l_1, \;l_2

连个子串我们用一个数组

f[i][j]

定义为：从

i

开始到

i+2^j-1

的区间opt后的结果

具象化：

假设现在

i=1

，那么在

2^0 \le j \le 2^{log_2n}

中被倍增为：

1.\;2,\;4,\;8,\;16\;......\;2^{log_2n}

为右端点的区间。

优化后的预处理为：

1\le i \le n,\,1 \le j \le log_2n,\;i \times j = n \times log_2 n \Rightarrow O(n\,log\,n)

我们再来看

n^2

的预处理做法，其中

1 \le i,\;j \le n

i\times j = n^2 \Rightarrow O(n^2)

优化做法有明显优势，用少空间记录了整个区间，所以我们叫这种数据结构为 ST表。

思路

step 1

我们以

2

为底数，做出一把把"尺子"：

CPP

lg[1] = 0
lg[2] = 1;
for(int i = 3; i < N; i++) 
    lg[i] = lg[i / 2] + 1;

这把尺子的长度

+\;i

等于需要计算的区间的右端点

j

step 2

初始化递推，不要忘记我们的定义式：数组 $f[i][j]$ 定义为：从 $i$ 开始到 $i+2^j-1$ 的区间opt后的结果：

CPP

for(int i = 1; i <= n; i++) 
   f[i][0] = a[i];

step 3

然后递推：

CPP

for(int j = 1; j <= logN; j++)
    for(int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

区间划分：将长度为 2^j 的区间 [i, i+2^j-1] 平分为两个长度为 2^(j-1) 的子区间

f[i][j] = \begin{cases} a[i], & \text{if } j = 0 \\ \min(f[i][j-1], f[i+2^{j-1}][j-1]), & \text{if } j > 0 \text{ (求最小值)} \\ \max(f[i][j-1], f[i+2^{j-1}][j-1]), & \text{if } j > 0 \text{ (求最大值)} \end{cases}

结果合并：整个区间的最大值就是两个子区间最大值的较大者

具象化：max(区间[i, i+2^j-1]) = max( max(左半区间), max(右半区间) )

step 4

查询：

CPP

  while(m--){
    int l, r;
    cin >> l >> r;
    int u = lg[r - l + 1]; // 合适长度的尺子
    int s1 = f[l][u];
    int s2 = f[r - (1 << u) + 1][u];
    cout << max(s1, s2) << "\n";
  }

找一把"尺子"，然后测量左右连个小区间的最大值，就结束了！

具体模版：

CPP

1  #include<bits/stdc++.h>
2  using namespace std;
3  
4  int const N = 1e5 + 7;
5  int const logN = 21;
6  int a[N], f[N][logN], lg[N];
7  int n, m;
8  
9  void init(){
10   lg[1] = 0, lg[2] = 1;
11   for(int i = 3; i < N; i++) lg[i] = lg[i / 2] + 1; // 规划"尺子"
12   for(int i = 1; i <= n; i++) f[i][0] = a[i]; // 递推初始化
13   for(int j = 1; j <= logN; j++)
14     for(int i = 1; i + (1 << j) - 1 <= n; i++)
15       f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
16       // 其中 f[i][j - 1] 为子串的左半边，f[i + (1 << (j - 1))][j - 1] 为右半边
17 }
18 
19 signed main(){
20   ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
21 
22   cin >> n >> m;
23   for(int i = 1; i <= n; i++) cin >> a[i];
24 
25   init();
26 
27   while(m--){
28     int l, r;
29     cin >> l >> r;
30     int u = lg[r - l + 1];
31     int s1 = f[l][u];
32     int s2 = f[r - (1 << u) + 1][u]; // 同理
33     cout << max(s1, s2) << "\n";
34   }
35 
36   return 0;
37 }

代码解释

第11行 的 "尺子"意为倍增法的间距，比如用步长为

2

的尺子计算每个区间长度为

2

的最大值

第15行

f[i][j - 1]

为左半边的小区间，

f[i + 2^{j - 1}][j - 1]

为右半边的小区间

总结

ST表通过倍增思想和动态规划的巧妙结合，成功将区间最值查询的时间复杂度从暴力法的O(nm)优化到：

预处理：O(n log n) 时间复杂度和空间复杂度
查询：O(1) 时间复杂度

核心优势

可重复贡献性：ST表利用区间重叠的特性，用两个子区间的结果组合出任意区间的答案
二进制优化：通过2的幂次划分，实现高效的空间利用和快速查询
静态数据处理：特别适合处理静态数据（数据不变）的区间查询问题

适用场景

ST表完美适用于：

静态数组的区间最大值/最小值查询（RMQ问题）
需要大量区间查询且要求快速响应的场景
可重复贡献问题（如GCD、按位与/或等）

ST表（稀疏表）笔记

文章操作