RMQ 算法

简介 #

RMQ 是 Range Maximum/Minimum Query 的缩写，意为区间的最大（或最小）值.

问题 #

已知数组 $A$ 中一共有 $n$ 个元素，给出 $m$ 次询问：

给出 $l,r$，求 $A[l\cdots r]$ 中的最大值.

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;
}

	暴力算法（$\color{red}{×}$）	`RMQ` 算法（$\color{green}{\sqrt{}}$）
预处理	$\color{green}{O(0)}$	$\color{green}{O(n\log{n})}$
单次查询	$\color{green}{O(n)}$	$\color{green}{O(1)}$
$m$ 次询问	$\color{red}{O(mn)}$	$\color{green}{O(m)}$

预处理 #

$f[i,j]$ 表示从 $A[i]$ 开始往后数 $2^j$ 个数的最大值，也就是 $\max\{A[i]\sim A[i+2^j-1]\}$.将 $2^j$ 个数从中间平均分成两部分，每一部分的元素为 $2^{j-1}$ 个.

$$\overbrace{\underbrace{A[i],A[i+1],\cdots,A[i+2^{j-1}-1]}_{{ 2^{j-1}}个元素},\underbrace{A[i+2^{j-1}],\cdots,A[i+2^j-1]}_{{ 2^{j-1}}个元素}}^{{ 2^j}个元素}$$

整个区间的最大值一定为左右两部分的最大值：

$$ f[i,j]=\max(f[i,j-1],f[i+2^{j-1},j-1]) $$

由于 $f[*,j]$ 是由 $f[*,j-1]$ 推出的，故第一层循环枚举 $j=0→\log{n}$.

初始条件	计算顺序	时间复杂度
$f[i,0]=A[i]$	$f[1→n,0→\log{n}]$	$O(n\log{n})$

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]\sim A[r]$ 的最大值.$A[l]\sim A[r]$ 一共有 $r-l+1$ 个元素，我们设 $s=\log(r-l+1)$，然后在整个区间内划出两个长度为 $2^s$ 的子区间：

根据前面的定义，左子区间的最大值为 $f[l,s]$，右子区间的最大值为 $f[r-2^s+1,s]$.

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

$$ \max\{A[l]\sim A[r]\}=\max(f[l,s],f[r-2^s+1,s]) $$

由于 $C++$ 提供的 $log2()$ 函数太慢，于是预处理 $Log[ \ ]$ 数组替代 $log2()$ 函数.

int Log[N]; // Log[i] = log2(i)

int pre() {
    ...
    Log[0] = -1; // 为了使 Log[1] = Log[1/2] + 1 = 0, Log[0] 得先赋值 -1
    for(int i = 1; i <= n; i ++)
        Log[i] = Log[i / 2] + 1;
}

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

模板 #

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

void pre() {
    Log[0] = -1; // Log[] 的预处理在这里
    for(int i = 1; i <= n; i ++)
        f[i][0] = a[i], Log[i] = Log[i / 2] + 1;

    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 = Log[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;
}