一维RMQ问题

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。
求区间最值最常用的是线段树（至少我是），但是今天学会了一个新的算法，写一篇博客纪念一下

方法：ST算法分成两部分：离线预处理（nlogn）和在线查询（O(1)）。虽然还可以使用线段树、树状链表等求解区间最值， 但是ST算法要比它们更快，而且适用于在线查询。

1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。
2）在线查询：对给定区间进行分割，借助该二维数组求最值。

（1）离线预处理：

ST算法使用DP思想求解区间最值，貌似属于区间动态规划，不过区间在增加时，每次并不是增加一个长度，而是使用倍增的思想，每次增加2^i个长度。
使用F[i,j]表示以i为起点，区间长度为2^j的区间最值，此时区间为[i,i + 2^j - 1]。
比如，F[0,2]表示区间[0,3]的最小值，即等于4，F[2,2]表示区间[2,5]的最小值，即等于1。
在求解F[i,j]时，ST算法是先对长度为2^j的区间[i,i + 2^j - 1]分成两等份，每份长度均为2^(j - 1)。之后在分别求解这两个区间的最值F[i,j - 1]和F[i + 2^(j - 1),j - 1]。最后在结合这两个区间的最值，求出整个区间的最值。特殊情况，当j = 0时，区间长度等于0，即区间中只有一个元素，此时F[i,0]应等于每一个元素的值。

举例：要求解F[1,2]的值，即求解区间[1,4] = {4,6,10,1}的最小值，此时需要把这个区间分成两个等长的区间，即为[1,2]和[3,4]，之后分别求解这两个区间的最小值。此时这两个区间最小值分别对应着F[1,1] 和 F[3,1]的值。

状态转移方程是 F[i,j] = min(F[i,j - 1],F[i + 2^(j - 1),j - 1])
初始状态为：F[i,0] = A[i]。

在根据状态转移方程递推时，是对每一元素，先求区间长度为1的区间最值，之后再求区间长度为2的区间最值，之后再求区间长度为4的区间最值….，最后，对每一个元素，在求解区间长度为log2^n的区间最值后，算法结束，其中n表示元素个数。
即：先求F[0][1]，F[1][1]，F[2][1]，F[3][1]，,，F[n][1]，再求.F[0][2]，F[1][2]，F[2][2]，F[3][2]，,，F[m][2]，… 。

（2）在线处理：

这里我们是已知待查询的区间[x,y]，求解其最值。
在预处理期间，每一个状态对应的区间长度都为2^i。由于给出的待查询区间长度不一定恰好为2^i，因此我们应对待查询的区间进行处理。
这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：（1）这两个小区间要能覆盖整个区间（2）为了利用预处理的结果，要求小区间长度相等且都为2^i。注意两个小区间可能重叠。

举例：待查询的区间为[3,11]，先尽量等分两个区间，则先设置为[3,7]和[8,11]。之后再扩大这两个区间，让其长度都等于为2^i。刚划分的两个区间长度分别为5和4，之后继续增加区间长度，直到其成为2^i。此时满足两个条件的最小区间长度为8,此时i = 3。
在程序计算求解区间长度时，并没有那么麻烦，我们可以直接得到i，即等于直接对区间长度取以2为底的对数。这里，对于区间[3,11]，其分解的区间长度为int（log(11 - 3 + 1)） = 3，这里log是以2为底的。

根据上述思想，可以把待查询区间[x，y]分成两个小区间[x，x + 2^i - 1] 和 [y - 2^i + 1，y] ，其又分别对应着F[x,i]和F[y - 2^i + 1,i]，此时为了求解整个区间的最小值，我们只需求这两个值得最小值即可，此时复杂度是O(1)。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=20001,M=21;
int f[N][M],n,a[N],x,ans,st,ed,m;
int logg(int x)
{
	int r;
	for(r=0;(1<<r)<=x;r++);
	return r-1;
}
int minn(int x,int y)
{
	if(x>y) return y;
	else return x;
}
int yuchuli()//首先利用倍增的思想对所有数进行预处理
{
	logg(n);
	//x=(int)(log(double(n))/log(2.0));
	for(int j=1;j<=x;++j)
	{
		for(int i=1;i<=n;++i)
		{
			if(i+(1<<j)-1<=n)
			f[i][j]=minn(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int rmq(int st,int ed)//直接求出[st,ed]区间内的最小值即可
{
	//x=(int)(log(double(ed-st+1))/log(2.0));
	logg(x);
	return ans=minn(f[st][x],f[ed-(1<<x)+1][x]);	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		f[i][0]=a[i];
	}
	yuchuli();	
	scanf("%d%d",&st,&ed);
	printf("%d",rmq(st,ed));
	return 0;
}

【例题1.】求m区间内的最小值

洛谷上的一道题，但是不能ac…………因为它是针对单调队列的所以RMQ爆空间了= =但是还是可以拿来练练手的，数据范围定小一点大概可以过5个点

【例题2.】Balanced Lineup

poj上标准的一道rmq裸题，附上代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int INF=0x7FFFFFFF;
int a,n,l,s,f[1010][1010],ma[1010][1010][6],mi[1010][1010][6],ans=INF;
inline int maxx(int x,int y,int z,int m)
{
	if(y>x)x=y;
	if(z>x)x=z;
	if(m>x)x=m;
	return x;
}
int logg(int x)
{
	int r;
	for(r=0;(1<<r)<=x;r++);
	return r-1;
}
inline int minn(int x,int y,int z,int m)
{
	if(y<x)x=y;
	if(z<x)x=z;
	if(m<x)x=m;
	return x;
}
inline int minnn(int a,int b)
{
	if(a>b) return b;
	else return a;
}
inline void yuchuli()
{
	for(int j=1,jt=1;jt<=n;++j,jt=(jt<<1))
	{
		for(int i1=1;i1+jt<=a;++i1)
		{
			for(int i2=1;i2+jt<=a;++i2)
			{
				ma[i1][i2][j]=maxx(ma[i1][i2][j-1],ma[i1][i2+jt][j-1],ma[i1+jt][i2][j-1],ma[i1+jt][i2+jt][j-1]);
				mi[i1][i2][j]=minn(mi[i1][i2][j-1],mi[i1][i2+jt][j-1],mi[i1+jt][i2][j-1],mi[i1+jt][i2+jt][j-1]);
			}
		}
	}
}
inline int solve(int i,int j)
{
	int l1=logg(n);//l1=(int)(log(double(n))/log(2.0));
	int k=(1<<l1),p=n;
	int m1=0,m2=INF;
	ans=INF;
	m1=maxx(ma[i][j][l1],ma[i][j+p-k][l1],ma[i+p-k][j][l1],ma[i+p-k][j+p-k][l1]);
	m2=minn(mi[i][j][l1],mi[i][j+p-k][l1],mi[i+p-k][j][l1],mi[i+p-k][j+p-k][l1]);
	ans=minnn(ans,m1-m2);	
	return ans;	
}
int main()
{
	int q;
	scanf("%d%d%d",&a,&n,&q);
	for(int i=1;i<=a;++i)
		for(int j=1;j<=a;++j)
		{
			int aa;
			scanf("%d",&aa);
			ma[i][j][0]=aa;
			mi[i][j][0]=aa;
		}
	yuchuli();
	for(int i=1;i<=q;++i)
	{
		int st,ed;
		scanf("%d%d",&st,&ed);
		printf("%d\n",solve(st,ed));
	}
	return 0;
}

二维RMQ问题

二维RMQ意思就是求一个矩形内的最值，它比起一维来讲，只是多了一个记录行数的数组罢了。
举例来说，有一个a*b矩阵，我们要求这个矩阵内一个n*n正方形的最大值，那么我们就用f[i][j][n]来表示第 i 行，从第 j 个数开始的n*n矩阵内的最大值，其实和一维没有差多少（才怪我调了N久QAQ）。

例题3.Cornfields

仍然是poj上一道RMQ二维裸题，题目大意是给你一个n*n的矩阵，让你从中圈定一个小矩阵，其大小为b*b，有Q个询问，每次询问告诉你小矩阵的左上角，求小矩阵内的最大值和最小值的差。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int INF=0x7FFFFFFF;
int a,n,l,s,f[1010][1010],ma[1010][1010][6],mi[1010][1010][6],ans=INF;
inline int maxx(int x,int y,int z,int m)
{
	if(y>x)x=y;
	if(z>x)x=z;
	if(m>x)x=m;
	return x;
}
inline int minn(int x,int y,int z,int m)
{
	if(y<x)x=y;
	if(z<x)x=z;
	if(m<x)x=m;
	return x;
}
inline int minnn(int a,int b)
{
	if(a>b) return b;
	else return a;
}
inline void yuchuli()
{
	for(int j=1,jt=1;jt<=n;++j,jt=(jt<<1))
	{
		for(int i1=1;i1+jt<=a;++i1)
		{
			for(int i2=1;i2+jt<=a;++i2)
			{
				ma[i1][i2][j]=maxx(ma[i1][i2][j-1],ma[i1][i2+jt][j-1],ma[i1+jt][i2][j-1],ma[i1+jt][i2+jt][j-1]);
				mi[i1][i2][j]=minn(mi[i1][i2][j-1],mi[i1][i2+jt][j-1],mi[i1+jt][i2][j-1],mi[i1+jt][i2+jt][j-1]);
			}
		}
	}
}
inline int solve(int i,int j)
{
	int l1=(int)(log(double(n))/log(2.0));
	int k=(1<<l1),p=n;
	int m1=0,m2=INF;
	ans=INF;
	m1=maxx(ma[i][j][l1],ma[i][j+p-k][l1],ma[i+p-k][j][l1],ma[i+p-k][j+p-k][l1]);
	m2=minn(mi[i][j][l1],mi[i][j+p-k][l1],mi[i+p-k][j][l1],mi[i+p-k][j+p-k][l1]);
	ans=minnn(ans,m1-m2);	
	return ans;	
}
int main()
{
	int q;
	scanf("%d%d%d",&a,&n,&q);
	for(int i=1;i<=a;++i)
		for(int j=1;j<=a;++j)
		{
			int aa;
			scanf("%d",&aa);
			ma[i][j][0]=aa;
			mi[i][j][0]=aa;
		}
	yuchuli();
	for(int i=1;i<=q;++i)
	{
		int st,ed;
		scanf("%d%d",&st,&ed);
		printf("%d\n",solve(st,ed));
	}
	return 0;
}

Criska

RMQ（ST算法）