RMQ

RMQ 问题是指：对于长度为 n 的数列 A，回答若干询问 RMQ (A , i , j ) ( i , j ≤ n)，返回数列A中下标在 i , j 里的最小（大）值，也就是说，RMQ问题是指求区间最值的问题。

二：st算法

ST算法是动态规划以及倍增的思想相结合。只适用于静态区间求最值，如果是动态的，需要用线段树。

2.1 基本思想

首先我们定义f[i][j]表示以下标i为起点，连续2^j个数中的最大值。eg：f[2][2]表示：从a[2]-a[5]的最大值。f[i][0]也就表示为a[i]了。

2.2 通过倍增的方法获取值

如我们想要取得a[2]-a[14]中间的最大值的话，如果我们能够二分的获得里面的值就好了比如a[2]-a[9],a[9]-a[14]，或者说a[2]-a[9],a[7]-a[14]的话就好了。这样我们取最大值就可以得到a[2]-a[14]的最大值了。
居然f[i][j]中的j代表2^j,又因为我们需要二分，很自然的想到了对数运算了。

那么我们可以得到查询的时候的方法：

//查询a[l]-a[r]的最大值
int query(int l,int r){
    int k = log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

2.3预处理

为了让我们能够实现2.2中的算法，我们需要对f[i][j]进行处理，使其支持区间查询操作。

//j的大小可以根据实际数据的范围来选择，一般数据为1e5,那么21位的完全够用
for(int j=1;j<=21;j++){
	//这里的n代表a[]的总长度，因此当前操作区间长度也就是i+(1<<j)-1
	//可以参考2.2中为什么+1,这就是为什么-1了。
        for(int i=1;i+(1<<j)-1<<n;i++)
            f[i][j] = max(f[i][j-1],f[i+1<<(j-1)][j-1]);
}

模板总结

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;

const int N = 1e5+10;
int f[N][21];
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int query(int l,int r){
    int k = log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}


int main(){
    int n,m;
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        f[i][0]=read();
    }

    for(int j=1;j<=21;j++){
        for(int i=1;i+(1<<j)-1<<n;i++)
            f[i][j] = max(f[i][j-1],f[i+1<<(j-1)][j-1]);
    }


    for(int i=1;i<=m;i++){
        int l=read();
        int r=read();
        printf("%d\n",query(l,r));
    }


    return 0;
}