RMQ即Range Minimum/Maximun Query，中文意思：查询一个区间的最小值/最大值
比如有这样一个数组：A{3 2 4 5 6 8 1 2 9 7}，然后问你若干问题：
数组A下标2~7区间最小的值是多少？ 最小值是（1）
数组A下标3~6区间最小的值是多少？ 最小值是（4）
数组A下标1~10区间最小的值是多少？ 最小值是（1）
......
专业术语：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。
这个问题其实可以用线段树轻松实现O(N)预处理，O（logN）查询，已经是很不错的复杂度了。
但是：有的时候查询操作很多，所以我们需要一个O（1）的查询算法。
那就是Sparse Table 即ST算法
ST算法是比较高效的在线算法。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。ST算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。
（一）首先是预处理，用动态规划（DP）解决。
设A[i]是要求区间最值的数列，F[i, j]表示从从i开始的连续2^j个数中的最大值。（DP的状态）
例如：A数列为：3 2 4 5 6 8 1 2 9 7 12 3 21
下标为：1 2 3 4 5 6 7 8 9 10 11 12 13
F[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是A数列中3这个数。同理：
F[1, 1] = max(3,2) = 3,
F[1，2]=max(3,2,4,5) = 5，
F[3，2]=max(4,5,6,8) = 8， F[3，2]表示从第三个数4开始连续（2^2）4个数中的最大值8
F[1，3] = max(3,2,4,5,6,8,1,2) = 8;
并且我们可以容易的看出F[i,0]就等于A[i]。（DP的初始值）
假如i=3，那么F[i, 0]=max(4,4)=4, A[3]=4, 所以DP的初值就是F[i,0]=A[i]
这样，DP的状态、初值都已经有了，剩下的就是状态转移方程。
我们把F[i，j]平均分成两段（因为F[i，j]一定是偶数个数字），
前半段为 i 到i + 2 ^ (j - 1) - 1， （请动手计算一下）
后半段为i + 2 ^ (j - 1)到i + 2 ^ j - 1 需要注意的是2 ^ (j - 1)和 2 ^ j - 1 的区别
前后段的长度都为2 ^ (j - 1)。
用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。
F[i，j]就是这两段各自最大值中的最大值。
于是我们得到了状态转移方程：
f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]);
方程前半段为f[i,j-1] 表示 从i 起连续2^(j-1)个数的最大值。
方程后半段f[i+2^(j-1),j-1] 表示从i + 2 ^ (j - 1)起连续2^(j-1)个数据的最大值。
然后取前后两段各自最大值中的最大值。
总结：求从i起连续2^j个数的最大值，就是把2^j 分成前后两个2^(j-1)，分别取其最大值，再通过比较获得此状态最大值。
我们先来学习个小知识点“<<”位移符号的使用
C或C++中：
<<可作为左移运算符 (向左移一位，右边自动补0)
比如：i<<4,是按位左移4位。
比如8<<4：
二进制状态下：
0000 0000 0000 1000 = 十进制8
↓
0000 0000 1000 0000 = 十进制128 128=8^4
十进制状态下：
1<<1 等价于 1*2^1
1<<2 等价于 1*2^2
3<<3 等价于 3*2^3
5<<4 等价于 5*2^4
听说位移"<<" 速度比乘法快。
注意+-运算符优先于<<符号
比如：5-1<<1等同(5-1)*2^1 ，而不是5-1*2^1
所以如果要表示 5-1*2^1，要写成5-(1<<1)
DP预处理的代码如下：请选择一种适合自己的方法作为模板。
//第一种写法：请理解好循环条件的意义
int n; //n是数组元素个数 int a[100004]; //数列 int f[100004][30]; //f[i][j] //f[i][j]表示以i为起点，区间长度为2^j的一段区间的最小（大）值 void RMQ_ST ( ) ////预处理ST表,数组中共n个元素 O(nlogn) { for (int i=1;i<=n;i++) f[i][0]=a[i];//dp初始值 for(int j=1;j<=20;j++) //为什么是20? 2^j最大可以是多大？ for ( int i = 1; i <= n; i++ ) //思考为什么外循环j套i，而不是外循环i套j if(i+(1<<j)-1<=n) //“<<”符号请看前面知识点 (1<<j)注意括号 { int s=i+(1<<(j-1)); //后半段的起点 等价 i+2^(j-1) f [i][j]=max ( f [i][j-1], f [s][j-1] ); //区间最大值，最小值用min函数 } }
//第二种写法：请理解好循环条件的意义
void RMQ_ST2 ( ) //预处理ST表,数组中共n个元素 O(nlogn) { for (int i=1;i<=n;i++) f[i][0]=a[i]; //dp初始值 for (int j=1;(1<<j)<=n; j++) //注意(1<<j)加上括号 for (int i=1;i+(1<<j)-1<=n;i++) // f [i][j]=max( f [i] [j-1], f [i+(1<<(j-1))] [j-1] );//求最小值是函数min }
这里我们需要注意的是循环的顺序，我们发现外层是j，内层所i，这是为什么呢？
可以是i在外，j在内吗？
答案是不可以。因为我们需要理解这个状态转移方程的意义。
状态转移方程的含义是：我们先得到F[i,0]（即1个元素）的值，然后通过2个1个元素的最值，获得所有长度为F[i,1]（即2个元素的最值），然后再通过2个2个元素的最值，获得所有长度为F[i,2]（即4个元素的最值），以此类推更新所有长度的最值。
而如果是i在外，j在内的话，我们更新的顺序就是F [1,0],F [1,1],F [1,2],F [1,3],表示更新从1开始的1个元素，2个元素，4个元素，8个元素(a[0],a[1],....a[7]）的最值，这跟我们的思维和计算方法完全不同，所以这样的方法肯定是错误的。
为了避免这样的错误，一定要好好理解这个状态转移方程所代表的含义。
（二）接着解决怎么样查询。
先看小知识：
幂：指乘方运算的结果。nm指将n自乘m次（针对m为正整数的场合）。把nm看作乘方的结果，叫做“n的m次幂”或“n的m次方”。
其中，n称为“底数”，m称为“指数”（写成上标）。当不能用上标时，通常写成n^m。
对数：如果 
，即a的x次方等于N（a>0，且a≠1），那么x叫做以a为底N的对数，记作
。其中，a叫做对数的底数，N叫做真数。
特别注意：如果在c或c++语言里，注意加上头文件cmath或math.h。
对数形式应该写成x=loga (N)，其中a是底数，(N)是真数，真数N一定要用（）。
比如x=log2 (8),那么x=3。注意：log和2之间不要有空格。
还可以写成另外一种形式：x=log(N) / log(a),真数和底数都要加括号，而且真数在前面，不建议用这个形式。
查询:
假设要查询从(i, j)这一段的最大值, 这个区间的长度我们可以计算得出是j - i + 1。
那么我们先求出一个最大的k, 使得k满足2^k <= (j - i + 1).
我们可以取k=log2( j - i + 1），举例说明：
要求区间[1，5]的最大值，k =(int)（log2（5 - 1 + 1））= 2。（计算机语言写法）,
(int)是用来向下取整。（想想为什么要向下取整）
我们就可以把[i, j]分成两个(部分重叠的)长度为2^k的区间: [i, i+2^k-1], [j-2^k+1, j];
比如查询数列A：5，6，7，8，9，我们可以查询(1, 4) 和(2, 5)这两个区间。
就是查询5 6 7 8和6 7 8 9 ，原数列左边界i和右边界j是不变的, 只是中间的三个数6 7 8重叠。
又比如数列B： 4 5 6 7 8 9 经计算数列B长度为 j-i+1=6，那么：
k=int(log2(j-i+1))=2 (int)是用来向下取整。（想想为什么要向下取整）
[i, i+2^k-1]区间计算后为[1,4] 包含元素为 4 5 6 7共4个。
[j-2^k+1, j]区间计算后为[3,6] 包含元素为 6 7 8 9 也是4个。
而我们之前dp预处理时已经求出了：
f(i, k)为区间[i, i+2^k-1]的最大值, 比如上面的f(1, 4)我们在预处理时已经求出来了。
f(j-2^k+1, k)为区间[j-2^k+1, j]的最大值，比如上面的f(2, 5)我们在预处理时也已经求出来了。
我们只要返回其中更大的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.
则有：RMQ(A, i, j)=max{ f [i , k], f [ j - 2 ^ k + 1, k]}。(伪代码)
又比如：要求区间[2，8]的最大值，k =(int)( log2（8 - 2 + 1）)= 2，
即求max (f [2, 2]，f [8 - 2 ^ 2 + 1, 2]) = max (f [2, 2]，f[5, 2])；
而f [2, 2]和f[5, 2]在前面已经预处理过了
请计算一下区间[1 ,11]的最大值，像上面一样手写过程。
查询代码如下：
int rmq_ask (int l, int r) //查询区间(l, r) { int k=(int) (log2(r-l+1)); //l->r区间长度---为2^k(向下取整) 千万记住对数一定要整体括起来 return max (f[l][k], f[r-(1<<k)+1][k]); //根据需要取min或者max }
ST算法解RMQ模板（洛谷1816 忠诚）
https://www.luogu.org/problemnew/show/P1816
P3865 【模板】ST表
https://www.luogu.org/problemnew/show/P3865
P3379 【模板】最近公共祖先（LCA）请用RMQ
https://www.luogu.org/problemnew/show/P3379
参考文章：
http://blog.csdn.net/qq_35776409/article/details/62890728
http://blog.csdn.net/u012860063/article/details/40752197