区间最值查询 RMQ

什么是RMQ

举个例子

给你一个长度为n (n≤50000)的序列，求区间[l,r]上的最大值，怎么求？So easy，\(O(n)\)扫一遍记录最大就可以了。

可是如果有Q (Q≤50000)次询问怎么办？这肯定过不了！所以我们就要用RMQ了。既然是一个面对多次查询的算法，那么为了提高查询的效率，都是要经过较长时间的预处理，RMQ也不例外，它拥有一个时间复杂度为\(O(nlogn)\)的预处理，然后可以在\(O(1)\)的时间内查询。下面我们来举一个简单的实例：

算法原理与代码实现

假设有一个数组\(a[9]=\{0,1,9,2,6,0,8,1,7\}\)

设数组dp[i][j]表示从第i位开始向后数\(2^j\)个数中的最小值。如dp[3][2]即表示从第三位（数字2）开始数4个数中最小的一个，即2，6，0，8中的最小值，这里是0，所以dp[3][2]=0。

既然我用了dp数组来表示，那么他是有递推方程的。可以这样来想，当前\(i\)点向右数\(2^j\)个中的最大值，可以表示成【\(i\)点向右数\(2^{j-1}-1\)个中的最大值和从\(i+2^{j-1}\)向右数\(2^{j-1}\)个中的最大值】中的最大值（有点绕，仔细看）

那么我们可以轻而易举的写出dp转移方程

$$dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])$$

然后就能轻而易举的写出代码:

（由于我没有找到这么裸的模板题，所以自己出一道）

题目描述：

已知一个长为n的队列，给出m次提问\(l,r\)，求区间[l,r]或[r,l]上的最值。 （n≤50000，m≤100000）

输入格式：

第一行两个整数n,m，第二行n个整数表示序列，接下来m行每行两个整数表示查询区间[l,r]（或[r,l]）

输出格式：

m行，第i行对应问题i的答案

建议你们自己写一下跑一下这两个数据，然后实在不会再看我的程序（我都讲得这么清楚明白怎么会不会呢？）

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=50010;
int n,m;
int a[M];
int dp[M][20];

int Read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

void RMQ(){
	for(int i=1;i<=n;i++)
		dp[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int main(){
//	freopen("testdata1.in","r",stdin);
//	freopen("testdata1.out","w",stdout);
	n=Read(),m=Read();
	for(int i=1;i<=n;i++)
		a[i]=Read();
	RMQ();
	for(int i=1;i<=m;i++){
		int l=Read(),r=Read(),k;
		if(l==r){
			printf("%d\n",a[l]);
			continue;
		}
		if(l>r) swap(l,r); 
		for(int i=1;i<=20;i++)
			if((1<<i)>=r-l+1){
				k=i-1;
				break;
			}
		int rr=r+1-(1<<k);
		printf("%d\n",max(dp[l][k],dp[rr][k]));
	}
	return 0;
}

是不是很简单呢？

拓展：求LCA

我们在最近公共祖先LCA一文中讲到，倍增求LCA是很常见的好写的算法，其时间复杂度是\(O((n+m)logn)\)，这里我们介绍的RMQ算法，则是可以以\(O(nlogn)\)的复杂度做预处理，\(O(1)\)的复杂度查询，看起来比倍增更快哦！

首先要介绍一个东西：DFS序

现在你有一个长得非常像cxk的树，这棵树的DFS序就是从根结点出发，DFS遍历是依次经过的节点的序列。比如这棵坤坤树的DFS序就是\(1，2，3，4，5，8，6，9，10，7\)或者\(1，6，7，9，10，2，4，5，8，3\)或者……，这些不同的DFS序都是对的，只不过取决于你先加入了哪条边等，但既然你用DFS序，那么他的顺序不同对答案是没有影响的！

很显然的我们可以想到DFS有一个性质，就是进入一个子树后不会再进入，因此一个子树中深度最浅的节点必定是这个子树的树根。又，我们能想到关于LCA的一个性质，就是\(LCA(a,b)\)一定是同时囊括a，b两点的一棵子树的根节点。【这里一定要想明白啊！！这里我说的“子树”是整个树的子树，意味着这里的“子树”也可以是整个树，表示节点a，b的LCA就是整个树的树根。】

所以知道了上面的两个性质，我们来思考一下LCA该如何用RMQ来求。

首先我们要来一个DFS序的加强版欧拉序（介绍我在链接里，我懒得再写一遍了），然后对欧拉序做RMQ的预处理，处理出从每一个点开始i向右数\(2^j\)个中的点的深度最小值。这就是预处理部分。

查询操作直接查询欧拉序上s[x]到s[y]区间上的深度最小的点，就是他们的LCA了！是不是很简单很神奇？？？

还是上一个我WA了100次的题： https://www.luogu.org/problem/SP14932
上代码：

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=2080;
bool vis[M<<1];
int n,m,q,cnt,now,rt;
int s[M<<1],deep[M<<1],el[M<<4],head[M<<1];
int dp[M<<1][20];
struct edge{
	int to,nxt;
	edge(){
		to=nxt=0;
	}
}e[M<<1];

int Read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline void Init(){
	now=cnt=0;
	memset(vis,false,sizeof(vis));
	memset(deep,0,sizeof(deep));
	memset(head,0,sizeof(head));
	memset(el,0,sizeof(el));
	memset(dp,0,sizeof(dp));
	memset(e,0,sizeof(e));
}

inline void Add(int x,int y){
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}

void DFS(int x){ 
	el[++now]=x;
	s[x]=now;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		deep[v]=deep[x]+1;
		DFS(v);
		el[++now]=x;
	}
}

void RMQ(){
	for(int i=1;i<=(n<<1);i++)
		dp[i][0]=el[i];
	for(int j=1;(1<<j)<=(n<<1);j++)
		for(int i=1;i<=(n<<1)+1-(1<<j);i++)
			dp[i][j]=deep[dp[i][j-1]]<=deep[dp[i+(1<<j-1)][j-1]]?dp[i][j-1]:dp[i+(1<<j-1)][j-1];
}

int main(){
	int T=Read();
	for(int sign=1;sign<=T;sign++){
		Init();
		n=Read();
		for(int i=1;i<=n;i++){
			m=Read();
			for(int j=1;j<=m;j++){
				int tmp=Read();
				vis[tmp]=true;
				Add(i,tmp);
			}
		}
		for(int i=1;i<=n;i++)
			if(!vis[i]){
				rt=i;
				break;
			}
		deep[rt]=1;
		DFS(rt);
		RMQ();
		q=Read();
		printf("Case %d:\n",sign);
		for(int i=1;i<=q;i++){
			int u=Read(),v=Read();
			if(u==v){
				printf("%d\n",u);
				continue;
			}
			if(s[u]>s[v]) swap(u,v);
			int k=log2(s[v]-s[u]+1);
			printf("%d\n",deep[dp[s[u]][k]]<=deep[dp[s[v]-(1<<k)+1][k]]?dp[s[u]][k]:dp[s[v]-(1<<k)+1][k]);
		}
	}
	return 0;
}

这个理论上比倍增复杂度低，但是好像跑出来我倍增20ms，这个30ms，不知道为什么。这个在写的时候还是看自己吧，觉得哪个好写就哪个！

完