RMQ 问题

RMQ（Range Maximum/Minimum Query），即区间最值查询。

给定一个长度为 n 的序列 {an}，每次询问给定 l, r，求 （或 max ）。

暴力做法每次询问 O(n)，q 次询问总复杂度 O(nq)，显然太慢了。

线段树可以做到 O(n) 建树、O(log n) 单次查询，总复杂度 O(n + qlog n)。

但如果没有修改操作，我们可以使用 ST 表 做到 O(nlog n) 预处理、O(1) 单次查询。

倍增思想

ST 表的核心是倍增。

倍增的基本思想是：预处理出长度为 2 的幂次的信息，查询时将任意区间拆成若干个预处理过的区间来合并。

一个直观的类比：任何正整数都可以用二进制表示，即拆成若干个 2 的幂次之和。倍增就是利用了这一点。

ST 表

预处理

例题：洛谷 P3865 【模板】ST 表。

定义 fi, j 表示从 ai 开始，长度为 2j 的区间的最大值，即

初始条件：fi, 0 = ai，即长度为 1 的区间最大值就是元素本身。

考虑递推。将区间 [i, i + 2j − 1] 从中间分成两半：

  • 左半部分 [i, i + 2j − 1 − 1]，对应 fi, j − 1；
  • 右半部分 [i + 2j − 1, i + 2j − 1]，对应 fi + 2j − 1, j − 1。

于是转移方程为 fi, j = max (fi, j − 1, fi + 2j − 1, j − 1)

预处理时，j 从小到大枚举（外层循环），i 从 1 到 n − 2j + 1 枚举（内层循环）。

为什么 j 在外层？

因为计算 fi, j 需要用到 f⋅, j − 1，必须保证 j − 1 层已经全部算完。

预处理时间复杂度 O(nlog n)，空间复杂度 O(nlog n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
int f[N][21]; // 2^20 = 1048576 > 1e6，一般够用
int Log[N];   // 预处理 log2

void build(int n) {
  Log[1] = 0;
  for (int i = 2; i <= n; ++i)
    Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; ++i)
    f[i][0] = a[i];
  for (int j = 1; j <= Log[n]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

关于预处理 log 

这里手动预处理了 ⌊log2i⌋。虽然 <cmath> 中有 log2() 函数，但它是浮点运算，既有精度问题又有常数问题。

也可以使用 __lg() 这个 GCC 内建函数，它返回的是 ⌊log2x⌋，速度很快。

查询

查询区间 [l, r] 的最大值。

令 k = ⌊log2(r − l + 1)⌋，则区间 [l, r] 可以被 [l, l + 2k − 1] 和 [r − 2k + 1, r] 两个长度为 2k 的区间覆盖。

这两个区间可能有重叠，但因为我们求的是 max ，重叠部分被算两次也不影响结果。

这也是 ST 表能做到 O(1) 查询的关键：max  和 min  具有可重复贡献的性质，即 max (a, a) = a。但像区间和这样的信息就不满足此性质，所以 ST 表不能用于区间求和。

query(l, r) = max (fl, k, fr − 2k + 1, k)

单次查询时间复杂度 O(1)。

1
2
3
4
int query(int l, int r) {
  int k = Log[r - l + 1];
  return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

const int N = 1e5 + 10;
int n, q, a[N];
int f[N][21], Log[N];

void build() {
  Log[1] = 0;
  for (int i = 2; i <= n; ++i)
    Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; ++i)
    f[i][0] = a[i];
  for (int j = 1; j <= Log[n]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r) {
  int k = Log[r - l + 1];
  return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  build();
  for (int l, r; q; --q) {
    std::cin >> l >> r;
    std::cout << query(l, r) << '\n';
  }
  std::cout.flush();
  return 0;
}

适用条件与局限

ST 表适用于静态 RMQ，即序列不会被修改的情况。

预处理 单次查询 支持修改
暴力 O(1) O(n) ✅
线段树 O(n) O(log n) ✅
ST 表 O(nlog n) O(1) ❌

如果需要支持修改，请使用线段树或树状数组。

更一般地，ST 表可以维护满足可重复贡献性质的信息，即满足 x ⊕ x = x 的运算 ⊕。常见的有：

  • max 、min 
  • gcd 、lcm
  • 按位与 &、按位或 |

拓展：二维 ST 表

晚点写。