RMQ 学习笔记

模板及讲解
运用st表实现区间询问区间最大/最小,初始化时间复杂度$O(nlogn)$, 查询$O(1)$
设$dp(i,j)$为从i开始长度为$2^j$的区间最小值,初始化合并结果即可,查询采用”两头补”方式
模板题:poj 3264

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 50000 + 5;
int n, q;
int h[MAXN], fmaxi[MAXN][25], fmini[MAXN][25];
//h为原数组,fmaxi[i][j]为从i开始长度为2^j的区间最小值
void initRMQ() {
for (int i=1;i<=n;i++) fmaxi[i][0] = fmini[i][0] = h[i];//初始值为原数组
for (int j=1;(1<<j)<=n;j++) {//j必定在外层
for (int i=1;i+(1<<j)-1<=n;i++) {
fmaxi[i][j] = max(fmaxi[i][j-1], fmaxi[i+(1<<(j-1))][j-1]);
fmini[i][j] = min(fmini[i][j-1], fmini[i+(1<<(j-1))][j-1]);//DP
}
}
}
int RMQMax(int x, int y) {
int k = (int)(log(y-x+1.0)/log(2.0));
return max(fmaxi[x][k], fmaxi[y-(1<<k)+1][k]);
}
int RMQMin(int x, int y) {
int k = (int)(log(y-x+1.0)/log(2.0));
return min(fmini[x][k], fmini[y-(1<<k)+1][k]);
}
void clear() {}
void init() {
clear();
for (int i=1;i<=n;i++) scanf("%d", &h[i]);
initRMQ();
}
void solve() {
for (int i=1;i<=q;i++) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", RMQMax(a, b) - RMQMin(a, b));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &q)==2&&n&&q) init(), solve();
return 0;
}

常见题型
1、求区间最大/最小值
Q:给出一个区间,询问某个子区间的最大/最小值。(没有修改操作)
解:因为不用修改,所以用RMQ$O(1)$查询最优,常数也小。
例题:poj 3264
2、求LCA
Q:给出一棵树,求两个节点的LCA。
解:
例题:

------ 本文结束 ------