RMQ 和 ST 表

· · 算法·理论

简介

RMQ，英文名 Range Min/Max Query，即区间最大值/最小值查询。

算法介绍

以区间最大值为例：

给定长度为 n 的一个数列 a，有 m 次查询，每次给定 l,r，求出 a_l,a_{l+1},\cdots,a_r 的最大值。n,m\le 10^5。

1. 暴力

这种方法不必赘述，单次查询时间复杂度为 O(n)，总复杂度 O(mn)，显然无法通过。

2. 分块

可以把 n 个元素分为若干段，分别维护最大值。假设每段有 k 个数，则共有 \left\lceil\dfrac{n}{k}\right\rceil 段。先 O(n) 预处理每一段的左右断端点、每个点属于哪个块、以及每个块内所有数的最大值。在每次查询时，暴力枚举不是整块的所有数，再枚举整块，复杂度为 O\left(k+\left\lceil\dfrac{n}{k}\right\rceil\right)，可以看出 k=\sqrt{n} 时最小。

这样总复杂度为 O(m\sqrt n)，但在本题中复杂度还是很高，只能通过 70\% 的数据。

3. ST 表

ST 表，英文名 Sparse Table，也称稀疏表。它是一种简单的数据结构，主要用于求解 RMQ 问题。它应用倍增的思想，可以 O(n\log n) 预处理、O(1) 查询。

使用一个二维数组 f(i,j)，表示从 a_i 开始连续 2^j 个数的最大值，即 \max\{a_i,a_{i+1},\dots,a_{i+2^j-1}\}。

预处理：

预处理时间复杂度为 O(n\log n)。

对于每一次查询 [l,r]，区间长度为 r-l+1，需要用几个区间进行完全覆盖。（注意：可以重复，因为最大值多算一次并不会影响答案，但是不能覆盖到区间外的元素）

令 tmp=\lfloor\log (r-l+1)\rfloor，可以用 [l,l+2^{tmp}-1] 和 [r-2^{tmp}+1,r] 进行完全覆盖。于是 \max\{a_l,a_{l+1},\dots,a_r\}=\max\{f(l,tmp),f(r-2^{tmp}+1,tmp)\}，可以 O(1) 得出。

总时间复杂度为 O(n\log n+m)，可以通过。

4. 一些提示

5. 代码实现

以下是 ST 表求解 RMQ 问题的代码。

const int N = 1e5 + 5;
int n, m;
int lg[N], p[N][20];
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        read(p[i][0]);
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            p[i][j] = max(p[i][j - 1], p[i + (1 << j - 1)][j - 1]);
    for (int i = 1; i <= m; i++) {
        int l, r;
        read(l), read(r);
        int tmp = lg[r - l + 1];
        write(max(p[l][tmp], p[r - (1 << tmp) + 1][tmp]));
        putchar('\n');
    }
    return 0;
}

题目练习