Appearance
简介
RMQ 是 Range Maximum/Minimum Query 的缩写,意为区间的最大(或最小)值。
问题
已知数组
- 给定
,求 。
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 算法( | |
---|---|---|
预处理 | ||
单次查询 | ||
预处理
将
整个区间的最大值为左右两部分的最大值:
- 边界条件:
; - 时间复杂度:
。
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]);
}
原理
现在我们要查询
设
左子区间的最大值为
虽然两个子区间有重叠部分,但它们包含了整个
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;
}