RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。
该篇文章主要讲一下ST (Sparse Table) 算法，复杂度 O(nlogn) - O(q) online。其核心就是动态规划。好吧，太久没写博客，刚刚帐号密码什么的都忘了，找回找了超久，本来不打算写的，可是因为怕自己学的也会忘记，所以就花点时间写写，上次是腿伦给我们上的课，可是早就忘记了，今天又回过头来看了一下，应该可以写点什么（不足的地方以后补充）。
进入正题，首先给你一串数字如 1 5 2 9 7 3 8 11 （下标从1 - 8），你要做的就是找出一段区间里面的最大最小值。于是， 你可以遍历一下， 于是你TLE了
。 所以 ， 你就要用到今天的RMQ 算法了，啦啦啦......
（一）首先，设F[i, j] 表示从第 i 个数起连续 2^j 个数中的最大值，如 i = 1, j = 2, 就是指 上述中下标为 1 到 4 的数，即 1 5 2 9 ，先看最大值（最小值同理），F[1, 0] = max(1) = 1, F[1, 1] = max(1, 5) = 5, F[1, 2] = max(1 5 2 9) = 9. 那么要怎么进行动态规划来实现呢?
我们把F[i，j]平均分成两段（因为f[i，j]一定是偶数个数字，不信的话可以自己试试
），从 i 到i + 2 ^ (j - 1) - 1为一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1)) ，举个栗子（炒的，很香）。比如i
= 1, j = 3时，F[1, 2] = max(1 5 2 9) = 9, F[4, 2] = max(7 3 8 11) = 11, 所以F[1, 3] = max(F[1, 2] , F[4, 2]) = 11; 状态转移方程为
F[i, j] = max( F[i，j-1], F[i + 2^(j-1)，j-1] ).
下面是一个特殊的例子（过程简略, 具体请自己模拟一遍，这也是一种很好的学习方法）
下面是具体实现代码( 请认真地模拟一遍，加深印象)
void rmq()
{
int tmp = (int)(log((double)n)/log(2.0));
for(i = 0; i < n; i ++)
max_node[i][0] = tt[i];
for(j = 1; j <= tmp; j ++)
{
for(i = 0; i < n; i ++)
if(i + (1 << (j - 1)) < n)
{
max_node[i][j] = max(max_node[i][j - 1], max_node[i + (1 <<(j - 1))][j - 1]);
}
}
}
（二）接下来就是RMQ 的Q( 查询 ) 了
假设query( i, j)， 我们可以取k = log2( j - i + 1)，则有：ans = max ( F[i , k], F[ j - 2 ^ k + 1, k] ) ，代码如下
int query(int i, int j)
{
int k = (int)(log((double)r - l + 1)/log(2.0));
int ans = max(max_node[l][k], max_node[r - (1 << k) + 1][k]);
return ans;
}
（三）例题 直接抛出题目链接和代码
http://poj.org/problem?id=3264 Balanced Lineup
题意 ：你求出一段区间里面的最大的差值
下面是渣渣的代码， 最好不要看，自己想的印象深刻一点哦
#include<stdio.h>
#include<string.h>
#include<math.h>
#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b
int i, j, k;
int n, m;
const int MAX = 100010;
int min_node[MAX][20]; // 后面的大小看 2 的n次方是否满足题目的要求即可
int max_node[MAX][20];
int tt[MAX];
void rmq()
{
int temp = (int)(log((double)n)/log(2.0));
for(i = 0; i < n; i ++)
min_node[i][0] = max_node[i][0] = tt[i];
for(j = 1; j <= temp; j ++)
{
for(i = 0; i < n; i ++)
if(i + (1 << (j - 1)) < n) // 这步判断感觉也挺重要的.没有会RE, 不信你试试
{
min_node[i][j] = min(min_node[i][j - 1], min_node[i + (1 <<(j - 1))][j - 1]);
max_node[i][j] = max(max_node[i][j - 1], max_node[i + (1 <<(j - 1))][j - 1]);
}
}
}
int find(int l, int r)
{
int k = (int)(log((double)r - l + 1)/log(2.0));
int Min = min(min_node[l][k], min_node[r - (1 << k) + 1][k]);
int Max = max(max_node[l][k], max_node[r - (1 << k) + 1][k]);
return Max - Min;
}
int main()
{
int left, right;
while(~scanf("%d%d",&n,&m))
{
for(i = 0; i < n; i ++)
{
scanf("%d",&tt[i]);
}
memset(min_node, 0, sizeof(min_node));
memset(max_node, 0, sizeof(max_node));
rmq();
while(m --)
{
scanf("%d%d",&left,&right);
printf("%d\n",find(left - 1, right - 1));
}
}
return 0;
}
常见问题 ：
1. 查找区间重复怎么办？
因为要二分，如果是数字串个数为奇数的话，难免会重复（如查询 1 5 2 9 11）， 你可能就要查询1 5 2 9 和 5 2 9 11，虽然有重复，但是效率还是比较高的
2. 一开始的数组怎么定义？
一般是这样的，int TT [ MAX ][ n ] ， 其中MAX 为该题的数据（稍微大一点 ，如 + 10），n 主要看 2 ^ n 要大于MAX，也不要去太大。
3 . 有没有什么要注意的事项？
在写法上，你有可能会用位运算，那你就要注意优先级了。如 6 - 1 << 2是多少？
答案是：6 * 2 * 2 = 24。所以我们要写成6 - (1 << 2)才是6 - 1 * 2 * 2 = 2 。要注意括号
4. 用途？
上面已讲，还可以去百度一下
5. 不懂， 有问题， LZ傻逼写错的怎么办
那就留言吧，傻傻的LZ 会回复傻傻的答案。
-------------------------------------------- 渣渣的算法路 ， 大神勿喷， 欢迎一起交流 ， 有事请留言