RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

 ST算法：先是预处理部分（构造RMQ数组），DP处理。假设b是所求区间最值的数列，dp[i][j] 表示从i到i+2^j -1中最值(从i开始持续2^j个数)。即dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]},或者dp[i][j]=max{dp[i][j-1],dp[i+2^(j-1)][j-1]}，这个过程的复杂度为：O(n(longn))

接着就是查询最值了，可以通过在O(1)完成查询。就是将查询区间[s,v]，分成两个2^k的区间。

以求最小值为例

#include
     
      #include
      
       #include
       
        using namespace std;#define M 100000#define MAXN 1000#define MAXM 1000int dp[M][20];void makermq(int n,int b[])//构造最值RMQ数组{    int i,j;    for(i=0;i
        
         =b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];       //求最小值            dp[i][j]=b[dp[i][j-1]]
         
          <<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1]; }int rmqIndex(int s,int v,int b[])//返回最值对应的下标{    int k=(int)(log((v-s+1)*1.0)/log(2.0));//求最大值   // return b[dp[s][k]]>=b[dp[v-(1<
         
        
       
      
     

代码没有给出主函数，主函数应根据具体题目要求来写。

以下是 poj3264：代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define M 50001int h[M];int dpmax[M][20],dpmin[M][20];void makermqmax(int n,int b[])//构造最值RMQ数组{    int i,j;    for(i=0;i