ST算法
RMQ问题
RMQ（Range Minimum/Maximum Query），即区间最值查询。对于长度为n的数列arr，回答若干询问Q(i,j)，返回数列arr中下标在i,j之间的最大/小值。如果只有一次询问，那一遍for就可以搞定，但是如果有多次询问就无法在很快的时间处理出来。
ST算法
ST算法是一个在线算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)的时间内回答每个查询，假设现在的数组为arr[] = {1,3,6,7,4,2,5,9}，算法步骤如下：
一、预处理（以处理区间最小值为例）
dpi表示从第i位开始连续2^j^个数（也就是到i+2^j^-1）中的最小值。例如dp2表示从第2个数开始，连续2个数的最小值，即3,6之间的最小值，即dp2=3，从dp数组的含义我们就知道，dpi=arr[i]（下标均是从1开始），初值有了，剩下的就是状态转移方程。首先把dpi平均分成两段（因为一定是偶数个数字），从i到i+2^j-1^-1为一段，i+2^j-1^到i+2^j^-1为一段（每段长度都为2^j-1^）。假设i=1,j=3时就是1,3,6,7和4,2,5,9这两段。dpi就是这两段最大值的最大值。于是得到了状态转移方程式dpi = max(dpi,dpi+2^j-1^)
for(int i = 1;i <= n;i++)
dp[i][0] = arr[i];
for(int j = 1;(1 << j) <= n;j++)
for(int i = 1;i + (1 << j) - 1 <= n;i++)
dp[i][j] = Math.min(dp[i][j-1],dp[i + (1<<(j - 1))][j-1]);二、查询
假设我们需要查询区间[L,R]中的最小值，令k=log~2~(R-L+1)，则区间[L,R]的最小值res=min(dpL,dpR-(1<<k)+1)，为什么这样就可以保证区间最值？dpL维护的是[L,L+2^k^-1]，dpL[k]维护的是[R-2^k^+1,R]，因此只要证明R-2^k^+1 ≤ l+2^k^-1即可，这里证明省略
int k = (int) (Math.log(r - l + 1) / Math.log(2));
int min = Math.min(dp_min[l][k],dp_min[r - (1 << k) + 1][k]);举个栗子
L=4,R=6，此时k=log~2~(R-L+1)=log~2~3=1，所以RMQ(4,6)=min(dp4,dp5)=min(4,2)=2，很容易看出来答案是正确的
题目链接：POJ3264
ST算法板子题，用java的同学要注意的就是把你所有会的输入输出优化全用上，不然会TLE 2333....
import java.io.InputStreamReader;
import java.util.Scanner;
public class CF522A {
final static int N = 50005;
static int[][] dp_min = new int[N][25];
static int[][] dp_max = new int[N][25];
public static void main(String[] args) {
Scanner cin = new Scanner(new InputStreamReader(System.in));
int n = Integer.parseInt(cin.next());
int m = Integer.parseInt(cin.next());
for(int i = 1;i <= n;i++) {
int tmp = cin.nextInt();
dp_min[i][0] = tmp;
dp_max[i][0] = tmp;
}
//预处理
for(int j = 1;(1 << j) <= n;j++)
for(int i = 1;i + (1 << j) <= n + 1;i++) {
dp_min[i][j] = Math.min(dp_min[i][j - 1],dp_min[i + (1 << j - 1)][j - 1]);//加减优先级高于位运算
dp_max[i][j] = Math.max(dp_max[i][j - 1],dp_max[i + (1 << j - 1)][j - 1]);
}
while((m--) != 0) {
int l = Integer.parseInt(cin.next());
int r = Integer.parseInt(cin.next());
int k = (int) (Math.log(r - l + 1) / Math.log(2));
int min = Math.min(dp_min[l][k],dp_min[r - (1 << k) + 1][k]);
int max = Math.max(dp_max[l][k],dp_max[r - (1 << k) + 1][k]);
System.out.println(max - min);
}
}
}