RMQ 算法 Balanced Lineup

Balanced Lineup

RMQ：

RMQ（Range Minimum/Maximum Query），即区间最值查询，这是一种在线算法，所谓在线算法，是指用户每次输入一个查询，便马上处理一个查询。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O（1）的时间内处理每次查询。

f[i][j]表示从i开始长度为（(1<<j)-1）的区间最值。

1. f[i][0]表示从i开始长度为1<<0的最值，f[i][0]=a[i];
2. 递推方程：f[i][j]=max/min( f[i][j-1] ,f[i+(1<<j)][j-1] ) ，区间（i，i+(1<<j) ） 的最值为 区间（i，i+1<<(j-1) -1）最值 与区间（i+ 1<<(j-1)，i+1<<j）最值较大/小的一个。                                     
3. 查询：区间为(l,r)，查询区间(l，l+1<<log(r-l) ) 和区间（r-(1<<log(r-l)+1,r）最值取最大/最小，eg： 查询[ 1, 12] ,我可以查询[1,8]和[5,12]（即取f[1][3]和f[5][3]），然后取两者较大一个。

RMQ不仅可以求区间最值，还可以用于区间求和，只要将递推方程取最值改为加即可，查询eg： 查询[1,13]区间和，取[1,8],[9,12]，[13][13] , 13=1101,所以取1个长度为1<<3的区间，一个长度为1<<2的区间，一个长度为1<<0 的区间

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e4+100;
const int INF=1e9;

int Max[N][20],Min[N][20];
int a[N];
int main(){
	int n,q;
	while(~scanf("%d%d",&n,&q)){
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			Max[i][0]=Min[i][0]=a[i];
		}
		for(int j=1;(1<<j)<=n;j++){
			for(int i=1;i<=n-(1<<j)+1;i++){
				Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
				Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
			}
		}
		int l,r,cnt;
		int res1,res2;
		while(q--){
			scanf("%d%d",&l,&r);
			cnt=(int)((double)log(r-l+1)/log(2.0));
			//cout<<cnt<<"..\n";
			res1=max(Max[l][cnt],Max[r-(1<<cnt)+1][cnt]);
			res2=min(Min[l][cnt],Min[r-(1<<cnt)+1][cnt]);
			printf("%d\n",res1-res2);
		}
	}
	return 0;
}

线段树解法：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=5e4+100;
const int INF=1e9;
#define Mid ((l+r)>>1)
#define left rt<<1,l,Mid
#define right rt<<1|1,Mid+1,r


int Max[N<<2],Min[N<<2];
void bulid(int rt,int l,int r){
	if(l==r){
		scanf("%d",&Max[rt]);
		Min[rt]=Max[rt];
		return ;
	}
	bulid(left);
	bulid(right);
	Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
	Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}

int ql,qr;
int res1,res2;
void query(int rt,int l,int r){
	if(l>=ql&&r<=qr){
		res1=max(Max[rt],res1);
		res2=min(Min[rt],res2);
		return ;
	}
	if(ql<=Mid) query(left);
	if(qr>Mid) query(right);
}
int main(){
	int n,q;
	while(~scanf("%d%d",&n,&q)){
		bulid(1,1,n);
		while(q--){
			scanf("%d%d",&ql,&qr);
			res1=0,res2=INF;
			query(1,1,n);
			printf("%d\n",res1-res2);
		}
	}
	return 0;
}