RMQ 区间最值问题：ST 表
前言
RMQ (Range Minimum/Maximum Query) 问题是指：
对于长度为 n 的数列 A ，回答若干询问 RMQ(A,i,j) (i,j\le n) ，返回数列 A 中下标在 i , j 里的最小（大）值，也就是说，RMQ问题是指求区间最值的问题。
时间复杂度: O(N)~O(logN)
主要方法
朴素（即搜索），
O(n)~O(qn)，online。线段树，
O(n)~O(qlogn)，online。ST （实质是动态规划），
O(nlogn)~O(q)，online。RMQ 标准算法：先规约成 LCA (Lowest Common Ancestor) ，再规约成约束 RMQ ，
O(n)-O(q)，online。
ST 算法
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e6+5,LogN=20; //表示定义整型常量，1e6+5即为10^6+5
int log[N],f[N][LogN+5],a[N];
int n,m,x,y;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]); //读入 n 个数据
log[0]=-1; //log[0] 设为 -1 ，这样才能使 log[1] 为 0
for(int i=1;i<=n;++i)
f[i][0]=a[i],log[i]=log[i>>1]+1; //预处理出长度为 1~n 的 log 值
for(int j=1;j<=LogN;++j) //计算 f[i][j]
for(int i=1;i+(1<<j)-1<=n;++i) //注意区间边界不能超过 n
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
//2j可以用右移运算符"<<"很快算出
//注意加减乘除运算符的优先级高于位移运算符
while(m--)
{
scanf("%d%d",&x,&y);
int s=log[y-x+1]; //求log2(y-x-1)下取整的值
printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s])); //回答每个提问
}
return 0;
}一、简介
ST 算法 (Sparse Table) 。
以求最大值为例，设 f[i,j] 表示 [i,i+2^j-1] 这个区间内的最大值，那么在询问到 [a,b] 区间的最大值时答案就是 max(f[a,k], f[b-2^k+1,k]) ，其中 k 是满足 2^k\le b-a+1 （即长度）的最大的 k ，即 k=[\frac{\ln(b-a+1)}{\ln(2)}] 。
f[][] 的求法可以用动态规划， f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]) 。
二、详细步骤
来看一下 ST 算法是怎么实现的（以最大值为例）：
首先是预处理，用一个 DP 解决。设 a 是要求区间最值的数列， f[i,j] 表示从第 i 个数起连续 2^j 个数中的最大值。
例如数列 3 2 4 5 6 8 1 2 9 7
f[1,0] 表示第 1 个数起，长度为 2^0=1 的最大值，其实就是 3 这个数。
f[1,1]=3 ， f[1,2]=5 ， f[1,3]=8 ， f[2,0]=2 ， f[2,1]=4 ……
从这里可以看出 f[i,0] 其实就等于 a[i] 。这样， DP 的状态、初值都已经有了，剩下的就是状态转移方程。
我们把 f[i,j] (j\ge 1) 平均分成两段（因为 j\ge 1时， f[i,j] 一定是偶数个数字），从 i 到 i+2^{j-1}-1 为一段， i+2^{j-1} 到 i+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 有什么用处，一般要想计算 max 还是要 O(logn) ，甚至 O(n) 。但有一个很好的办法，做到了 O(1) 。
还是分开来。如在上例中我们要求区间 [2,8] 的最大值，就要把它分成 [2,5] 和 [5,8] 两个区间，因为这两个区间的最大值我们可以直接由 f[2,2] 和 f[5,2] 得到。
扩展到一般情况，就是把区间 [l,r] 分成两个长度为 2^n 的区间（保证有 f 对应）。直接给出表达式：
k=floor(ln(r-l+1)/ln(2));
ans=max(f[l][k],f[r-2^k+1][k]);这样就计算了从 l 开始，长度为 2^k 的区间和从 r-2^k+1 开始长度为 2^k 的区间的最大值，二者中的较大者就是整个区间 [l,r] 上的最大值。
三、算法流程
预处理
实质：动态规划
设 a[1...n] ，设 f[i][j] 表示从 a[i] 到 a[i+2^j-1] 最大值，共 2^j 个。
由于共 2^j 个，可将其分成两份，分别是 f[i][j-1] 和 f[i+2^(j-1)][j-1] 。
状态转移方程：
f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])
边界条件为 f[i][0]=a[i]
时间复杂度 O(nlogn)
询问
若我们询问区间 [l,r] 的最大值，则先求出最大的 x 满足 2^x\le r-l+1 ，那么区间 [l,r]=[l,l+2^x-1]\cup [r-2^x+1,r]
那么 [l,r] 的最大值为 max(f[l][x],f[r-2^x+1][x])，可在 O(1) 内算出。
虽然有交集，但并不影响，这就是 ST 算法只适用于求区间最值的原因。
对于求区间 [x,y]
K=log2(y-x+1)
ans=max(f[x][k],f[y-2^k+1][k])
技巧
因为 cmath 库中的 log2() 函数效率不高，所以除了调用 log2() 函数外，通常还会使用 O(N) 递推预处理出 1\ldots N 这 N 种区间长度各自对应的 k 值。具体地，设 log[d] 表示 \log_2(d) 向下取整，则 log[d]=log[d/2]+1 。
注：部分资料来源于百度百科