前言
大概是去年十月份开始，开始刷起了leetcode。当时，主要是两个目的，一是加强自己的思维能力，个人觉得算法还是很有意思的，二是开始在日常工作中使用python写些脚步来处理些重复的劳动，借此去学习学习python（不过后面打着打着就开始用java了，蛋疼）。
以前打比赛常用到RMQ算法，不过当时都没有深入了解过原理，前段时间仔细看了看原理和以前的模版，特地整理了一下，在O(1)的时间复制度实现区间最值查询，真的很巧妙
算法简介
st算法网上有时也叫RMQ算法，即区间最值查询（Range Minimum/Maximum Query），其实st算法并不等于rmq算法，st算法为区间最值的问题提供了一个很好解决方案，其本质是一个动态规划。其中预处理的时间复杂度是O(n*log(n))，查询的时间复杂度是O(1)
##算法讲解
假设给定的数组为arr[i]，单次查询[l,r]区间内的最大值
预处理
dp[i,j]代表arr[i]开始，总共$2^j$数中的最大值
状态转移方程为：dp[i,j]=max(dp[i,j-1],dp[i+$2^{j-1}$,j-1])
该方程的意思即：arr[i],arr[i+1]……arr[i+$2^j$-1]数组可以分为两个子数组分别求最大值
可以对上述公式进行展开：
dp[i,j]:arr[i],arr[i+1]……arr[i+$2^j$-1]
dp[i,j-1]:arr[i],arr[i+1]……arr[i+$2^{j-1}$-1]
dp[i+$2^{j-1}$,j-1]:arr[i+$2^{j-1}$],arr[i+$2^{j-1}$+1]……arr[i+$2^j$-1]
区间查询
那么对于区间[l,r]中最大值的查询，我们可以这么理解：求以下两个子区间中的最大值
[l,k1],[k2,r]. (k1<=k2)
基于此，我们可以想到给(r - l + 1)取以2为底的对数，令t=$log_2{(r-l+1)}$，即可得到k1,k2
[l,l+$2^t$-1],[r-$2^t$+1,r]
[l,r]区间中的最大值即为:max(dp[l,t],dp[r-$2^t$+1,t])
算法实现
public int[][] dp = new int[N][31];
void rmq_init(int[] arr) {
int l = arr.length;
for (int i = 0; i < l; i++) {
dp[i][0] = arr[i];//初始化
}
for (int j = 1; (1 << j) <= l; j++) {
for (int i = 0; i + (1 << j) - 1 <= l; i++) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
int rmq(int l, int r) {
int k = (int) (Math.log((double) r - l + 1) / Math.log(2.0));
return Math.max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
以上即为对st算法介绍，至此，其实除了rmq问题，对于区间求最大公倍数，最小公约数，st算法也同样适用。其实类似这种区间查询，以前还常常使用线段树，O(log(n))的效率也是很可观的
偷偷放张最新的排名图（菜鸡也能上分，哈哈）：
