?RMQ(Range Minimum/Maximum Query)問(wèn)題是指：對(duì)于長(zhǎng)度為n的數(shù)列A，回答若干詢問(wèn)RMQ(A,i,j)(i,j<=n)，返回?cái)?shù)列A中下標(biāo)在[i,j]里的最小(大)值。
最簡(jiǎn)單的算法我就不解釋了，直接搜。但是對(duì)于數(shù)據(jù)量非常大時(shí)，這種方法并不適用。所以我們可以使用線段樹(shù)來(lái)記錄這個(gè)最大（小）值，效率咋算我還不是很了解，反正是一個(gè)nlogn形式的。但是線段樹(shù)的建立和查詢都是這個(gè)效率。不過(guò)有一個(gè)更好的方法，那就是ST算法（Sparse Table）：它是一種動(dòng)態(tài)規(guī)劃的方法。以最小值為例。a為所尋找的數(shù)組，用一個(gè)二維數(shù)組f(i,j)記錄區(qū)間[i,i+2^j-1]區(qū)間中的最小值。其中f[i,0] = a[i];
所以，對(duì)于任意的一組(i,j)，f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)}來(lái)使用動(dòng)態(tài)規(guī)劃計(jì)算出來(lái)。
這個(gè)算法的高明之處不是在于這個(gè)動(dòng)態(tài)規(guī)劃的建立，而是它的查詢：它的查詢效率是O(1)！如果不細(xì)想的話，怎么弄也是不會(huì)想到有O（1）的算法的。假設(shè)我們要求區(qū)間[m,n]中a的最小值，找到一個(gè)數(shù)k使得2^k<n-m+1，這樣，可以把這個(gè)區(qū)間分成兩個(gè)部分：[m,m+2^k-1]和[n-2^k+1,n]！我們發(fā)現(xiàn)，這兩個(gè)區(qū)間是已經(jīng)初始化好的！前面的區(qū)間是f(m,k)，后面的區(qū)間是f(n-2^k+1,k)！這樣，只要看這兩個(gè)區(qū)間的最小值，就可以知道整個(gè)區(qū)間的最小值！
不得不佩服想出這個(gè)算法的人啊！
具體的代碼可以看poj 3264。
不過(guò)還是要說(shuō)幾個(gè)注意的地方：
開(kāi)辟這個(gè)二維數(shù)組f的時(shí)候注意其第二維不要開(kāi)的過(guò)大，因?yàn)?的指數(shù)會(huì)很大的，到時(shí)候在自己機(jī)器上都無(wú)法運(yùn)行。
在動(dòng)態(tài)規(guī)劃計(jì)算數(shù)組f的時(shí)候，用對(duì)2取對(duì)數(shù)來(lái)計(jì)算上面說(shuō)的k，那樣速度好一點(diǎn)。計(jì)算出k后，注意對(duì)循環(huán)控制變量的范圍控制，而且一旦超出了范圍，那么該值便不必計(jì)算。
算指數(shù)的時(shí)候可以用>>和<<來(lái)計(jì)算，不過(guò)注意加括號(hào)。
在查詢的時(shí)候，k值仍然可以用對(duì)2取對(duì)數(shù)。

?

例程：pku 3264
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define maxn 50001
int a[maxn];
int dpmax[maxn][40];
int dpmin[maxn][40];
int getmin(int a,int b)
{
??? if(a<b) return? a;
??? else??? return? b;???
}
int getmax(int a,int b)
{
??? if(a>b) return? a;
??? else??? return? b;???
}
void Make_Big_RMQ(int n)
{
??? int i,j,k;
??? for(i=1;i<=n;i++)? dpmax[i][0]=a[i];
??? for(j=1;j<=log((double)n)/log(2.0);j++)
??????? for(i=1;i+(1<<j)-1<=n;i++)
??????? {
??????????? dpmax[i][j]=getmax(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
??????? }???
}
void Make_Min_RMQ(int n)
{
??? int i,j,k;
??? for(i=1;i<=n;i++)? dpmin[i][0]=a[i];
??? for(j=1;j<=log((double)n)/log(2.0);j++)
??????? for(i=1;i+(1<<j)-1<=n;i++)
??????? {
??????????? dpmin[i][j]=getmin(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
??????? }???
}
int get_big_rmq(int a,int b)
{
??? int k=(int)(log((double)(b-a+1))/log(2.0));
??? return getmax(dpmax[a][k],dpmax[b-(1<<k)+1][k]);
}
int get_min_rmq(int a,int b)
{
??? int k=(int)(log((double)(b-a+1))/log(2.0));
??? return getmin(dpmin[a][k],dpmin[b-(1<<k)+1][k]);
}
int main()
{
??? int n,m,i,j,k,q,x,y;
??? while(scanf("%d%d",&n,&q)!=EOF)
??? {
??????? for(i=1;i<=n;i++)
??????? scanf("%d",&a[i]);
??????? Make_Big_RMQ(n);
???????
??????? Make_Min_RMQ(n);
???????
??????? for(i=1;i<=q;i++)
??????? {
??????????? scanf("%d%d",&x,&y);
??????????? printf("%d\n",get_big_rmq(x,y)-get_min_rmq(x,y));???
??????? }??
???????
??? }
???
???
??? return 0;???
}