RMQ问题之ST算法
ST算法的基本原理百度一下就可以知道
RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。可以写一个线段树，但是预处理和查询的复杂度都是O（logn)。这里有更牛的算法，就是ST算法，它可以做到O(nlogn)的预处理，O(1)！！！地回答每个询问。
来看一下ST算法是怎么实现的(以最大值为例）：
首先是预处理，用一个DP解决。设a[i]是要求区间最值的数列，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，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出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）)。用上例说明，当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-i)，j-1]）.
接下来是得出最值，也许你想不到计算出f[i，j]有什么用处，一般毛想想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2^n的区间（保证有f[i，j]对应）
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define eps 1e-5#define MAXN 55555#define MAXM 11111#define INF 1000000000#define lch(x) x<<1#define rch(x) x<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int mi[MAXN][17], mx[MAXN][17], w[MAXN];int n, q;void rmqinit(){ for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = i; int m = (int)(log(n * 1.0) / log(2.0)); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) { mx[j][i] = mx[j][i - 1]; mi[j][i] = mi[j][i - 1]; if(j + (1 << (i - 1)) <= n) { if(w[mx[j][i]] < w[mx[j + (1 << (i - 1))][i - 1]]) mx[j][i] = mx[j + (1 << (i - 1))][i - 1]; if(w[mi[j][i]] > w[mi[j + (1 << (i - 1))][i - 1]]) mi[j][i] = mi[j + (1 << (i - 1))][i - 1]; } }}int rmqmin(int l,int r){ int m = (int)(log((r - l + 1) * 1.0) / log(2.0)); if(w[mi[l][m]] > w[mi[r - (1 << m) + 1][m]]) return mi[r - (1 << m) + 1][m]; else return mi[l][m];}int rmqmax(int l,int r){ int m = (int)(log((r - l + 1) * 1.0) / log(2.0)); if(w[mx[l][m]] < w[mx[r - (1 << m) + 1][m]]) return mx[r - (1 << m) + 1][m]; else return mx[l][m];}int main(){ scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) scanf("%d", &w[i]); rmqinit(); int l, r; while(q--) { scanf("%d%d", &l, &r); printf("%d\n", rmqmax(l, r)); } return 0;}