RMQ:范围最小值问题。给出一个n个元素的数组A1,A2,...,An，设计一个数据结构支持查询操作Query(L,R):计算min{AL,AL+1,...,AR}。
每次用一个循环来求最小值显然不够快快，前缀和的思想也不能提高效率，这时候ST算法就派上用场了，它预处理的时间是O(nlogn)，但是查询只需要Q（1），而且常数很小。
令dp[i][j]表示从i开始的，长度为2^j的一段元素中的最小值，递推公式：dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]}
模板代码：
void RMQ_init(const vector<int> &A)
{
int n=A.size();
for(int i=;i<n;++i)
d[i][]=A[i];
for(int j=;(<<j)<=n;++j) //长度
for(int i=;i+(<<j)- <= n;++i) //起点，虽然书上写的是 < n
d[i][j]=min(d[i][j-],d[i+(<<(j-))][j-]);
}
int RMQ(int L,int R)
{
int k=;
while((<<(k+))<=R-L+) k++; //int k=(int)((log(R-L+1))/log(2.0));
return min(d[L][k],d[R-(<<k)+][k]);
}
模板题：南阳理工119
题意：求一段区间内的最大值和最小值之差，所以统计最大值和最小值分别用RMQ来统计
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Max = + ;
int maxsum[Max][],minsum[Max][];
int n,q,v;
void RMQ_init()
{
for(int j = ; ( << j) <= n; j++)
{
for(int i = ; i + ( << j) - <= n; i++)
{
maxsum[i][j] = max(maxsum[i][j - ], maxsum[i + ( << (j - ))][j - ]);
minsum[i][j] = min(minsum[i][j - ], minsum[i + ( << (j - ))][j - ]);
}
}
}
int RMQ(int l, int r)
{
int k = ;
while( ( << (k + )) <= (r - l + ))
k++;
int maxn = max(maxsum[l][k], maxsum[r - ( << k) + ][k]);
int minn = min(minsum[l][k], minsum[r - ( << k) + ][k]); return maxn - minn;
}
int main()
{
while(scanf("%d%d", &n, &q) != EOF)
{
for(int i = ; i <= n; i++)
{
scanf("%d", &v);
minsum[i][] = maxsum[i][] = v;
}
RMQ_init();
while(q--)
{
int a,b;
scanf("%d%d", &a, &b);
printf("%d\n", RMQ(a,b));
}
}
return ;
}