简介

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

问题

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

• 给定 $l,r$，求 $max\{A[l],\cdots ,A[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;
}

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

预处理

$f[i,j]$：$A[i]$ 开始往后 $2^j$ 个数的最大值，也就是 $max\{A[i]\cdots A[i+2^j-1]\}$。

将 $2^j$ 个数从中间平均分成两部分，每部分有 $2^{j-1}$ 个元素。

$$\underset{2^{j-1}}{\underbrace{A[i],\cdots ,A[i+2^{j-1}-1]}},\underset{2^{j-1}}{\underbrace{A[i+2^{j-1}],\cdots ,A[i+2^j-1]}}$$

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

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

• 边界条件：$f[i,0]=A[i]$；
• 时间复杂度：$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]\cdots A[r]$ 的最大值。

设 $s=\lfloor {\log }_2(r-l+1)\rfloor$，然后划出两个长度为 $2^s$ 的子区间：

$$\begin{array}{r}A[l],\cdots ,A[r-2^s+1],\cdots ,A[l+2^s-1],\cdots ,A[r]\stackrel{2^s}{\overbrace{\phantom{A[l],\cdots ,A[r-2^s+1],\cdots ,A[l+2^s-1]}}}\phantom{,\cdots ,A[r]}\phantom{A[l],\cdots ,}\underset{2^s}{\underbrace{\phantom{A[r-2^s+1],\cdots ,A[l+2^s-1],\cdots ,A[r]}}}\end{array}$$

左子区间的最大值为 $f[l,s]$，右子区间的最大值为 $f[r-2^s+1,s]$。

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

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

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

模板

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