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|1
using 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] = w[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];
            if(j + (1 << (i - 1)) <= n) mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);
            mi[j][i] = mi[j][i - 1];
            if(j + (1 << (i - 1)) <= n) mi[j][i] = min(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));
    return min(mi[l][m] , mi[r - (1 << m) + 1][m]);
}
int rmqmax(int l,int r)
{
    int m = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return max(mx[l][m] , mx[r - (1 << m) + 1][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;
}

至于要返回下标呢

其实稍微改动一下就行了

#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|1
using 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;
}