Skip to content

RMQ 算法

2021-05-02

简介

RMQ 是 Range Maximum/Minimum Query 的缩写,意为区间的最大(或最小)值。

问题

已知数组 A 中一共有 n 个元素,给出 m 次询问:

  • 给定 l,r,求 max{A[l],,A[r]}
cpp
int n, a[];

// 暴力算法
void query(int l, int r) {
    int ans = a[l];
    for (int i = l; i <= r; i ++)
        ans = max(ans, a[i]);
    return ans;
}
暴力算法(×RMQ 算法(
预处理O(0)O(nlogn)
单次查询O(n)O(1)
m 次询问O(mn)O(m)

预处理

f[i,j]A[i] 开始往后 2j 个数的最大值,也就是 max{A[i]A[i+2j1]}

2j 个数从中间平均分成两部分,每部分有 2j1 个元素。

A[i],,A[i+2j11]2j1,A[i+2j1],,A[i+2j1]2j1

整个区间的最大值为左右两部分的最大值:

f[i,j]=max{f[i,j1],f[i+2j1,j1]}
  • 边界条件:f[i,0]=A[i]
  • 时间复杂度:O(nlogn)
cpp
const int N = 1e6 + 1, logN = 32;
int n, a[N], f[N][logN];

void pre() {
    for (int i = 1; i <= n; i ++)
        f[i][0] = a[i];
    
    for (int j = 1; j < logN; j ++) // f[][] 的第 2 维一定要先枚举
        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]);
}

原理

现在我们要查询 A[l]A[r] 的最大值。

s=log2(rl+1),然后划出两个长度为 2s 的子区间:

A[l],,A[r2s+1],,A[l+2s1],,A[r]A[l],,A[r2s+1],,A[l+2s1]2s,,A[r]A[l],,A[r2s+1],,A[l+2s1],,A[r]2s

左子区间的最大值为 f[l,s],右子区间的最大值为 f[r2s+1,s]

虽然两个子区间有重叠部分,但它们包含了整个 [l,r] 区间。因此

max{A[l],,A[r]}=max{f[l,s],f[r2s+1,s]}
cpp
int query(int l, int r) { // 返回 a[l] ~ a[r] 的最大值
    int s = log2(r - l + 1);
    return max(f[l][s], f[r - (1 << s) + 1][s]);
}

模板

cpp
const int N = 1e6, logN = 32;
int n, l, r, a[N], f[N][logN];

void pre() {
    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]);
}

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    pre();
    while (cin >> l >> r)
        cout << query(l, r) << endl;
}