RMQ算法
引入：
例1、题目描述
输入N个数和M次询问，每次询问一个区间[L,R],求第L个数到R个数之间的最大值。
第一种方法：大暴力之术。 但是……时间复杂度最坏会达到 $O（NM）$，一半左右的点绝对爆T。
所以，引入了————RMQ！
RMQ：Range Maximum(Minimum) Query的缩写，顾名思义是用来求某个区间内的最大值或最小值，通常用在需要多次询问一些区间的最值的问题中。
RMQ的原理是 动态规划
用A[1..N]表示一组数，F[I,J]表示从A[I]到A[I+2^J-1]这个范围内的最大值，也就是以A[I]为起点连续2^J个数的最大值，由于元素个数为2^J个，所以从中间平均分成两部分，每一部分的元素个数刚好为2^(J-1)个，如下图：
整个区间的最大值一定是左右两部分最大值的较大值，满足动态规划的最优原理
状态转移方程：
F[I,J]=max(F[I,J-1],F[I+2^(J-1),J-1])
边界条件为F[I,0]=A[I]
这样就可以在 $O(NlgN)$ 的时间复杂度内预处理F数组。
预处理F数组代码：
For i:=1 to n do f[I,0]:=a[i]
for j:=1 to trunc(ln(n)/ln(2)) do begin // 用到了换底公式，数学果然很重要
for i:=1 to n+1-1 shl j do
f[I,j]:=max(f[I,j-1],f[i+1 shl (j-1),j-1])
End;
对于询问[L,R],求出最大的x,满足2^x<=R-L+1,即x=trunc(ln(R-L+1)/ln(2))
[L,R]=[L,L+2^x-1] ∪[R+1-2^x,R]，两个子区间元素个数都是2^x个，如图
ANS(L,R)=max(F[L,x],F[R+1-2^x,x])
注意：在这里，RMQ在取最大最小值时，区间允许有重叠，但是求区间和的时候，坚决不能重叠，后果不用说。
询问操作代码：
Function query(L,R:longint):longint;
Var x:longint;
Begin
x:=trunc(ln(R-L+1)/ln(2));
exit(max(f[L,x],f[R+1-1 shl x,x]))
End;
该问题总时间复杂度为O(NlgN+M)，避免了暴力超时的问题，而且一般比线段树$ (M*lgN) $略快。
<Marvolo原创，严禁转载>