RMQ (Range Minimum/Maximum Query)問題是指：對于長度為n的數(shù)列A弥姻，回答若干詢問RMQ(A,i,j)(i,j<=n)缅疟，返回數(shù)列A中下標(biāo)在[i,j]里的最小(大）值梗顺，也就是說宵荒，RMQ問題是指求區(qū)間最值的問題 采郎。
解決這類問題常用的是tarjan的Sparse_table算法,即稀疏表算法懂昂。
它的預(yù)處理時間是O( nlogn ),但是查詢時間為O( 1 )
Balanced Lineup
#include <cstdio>
#include<algorithm>
#include <stdlib.h>
#include<string.h>
#define maxn 50005
using namespace std;
int dmin[maxn][16],dmax[maxn][16];
int rmq_min(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1) k++;//如果2^(k+1)<=r - l + 1,那么k還可以加1
//可以保證2^k最大等于區(qū)間長度,那么范圍查詢不越界,且左右半邊至少無空隙
return min(dmin[l][k],dmin[r-(1<<k)+1][k]);
}
int rmq_max(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1) k++;
return max(dmax[l][k],dmax[r-(1<<k)+1][k]);
}
int main()
{
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
dmin[i][0]=a;
dmax[i][0]=a;
}
for(int j=1;(1<<j)<=n;j++)
{
for(int i=0;i+(1<<j)-1<n;i++)
{
dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);
dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
}
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",rmq_max(a-1,b-1)-rmq_min(a-1,b-1));
}
}
