RMQ问题 ST表

RMQ（Range Minimum/Maximum Query）

区间最值查询问题
用ST表解决问题，专门用来解决区间最值问题。对数列进行O(nlogn)处理，O(1)查询。ST表可以解决的问题，线段树，树状数组都可以解决，但后两者都是O(nlogn)处理，O(mlogm)查询。
ST表是利用倍增的思想。设数组f[i][j]，表示以元素i开头的，长度为2^j区间内的最值。枚举长度因子j，f[i][j] = max(f[i][j-1]+f[i+(1<<j)][j]).
具体看代码！
洛谷P3865 ST表

#include <bits/stdc++.h>
using namespace std;
#pragma GCC Opimize(2);
const int maxn = 1e5+15;
int f[maxn][21];
int read(){
    int f=1,x=0;char s=getchar();
    while (s<'0' || s>'9'){
        if (s=='-') f = -1;
        s=getchar();
    }
    while (s>='0' && s<='9'){
        x = x*10 + s - '0';
        s=getchar();
    }
    return x*f;
}
inline int max(int a,int b){
    return a>b?a:b;
}
inline int query(int l,int r){
    int x = r-l+1,k;
    for (k=0;x>1;k++)
        x >>= 1;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    int n,m,l,r;
    //scanf ("%d %d",&n,&m);
    n = read(),m = read();
    for (int i=1;i<=n;i++)  //scanf ("%d",&f[i][0]);
        f[i][0] = read();
    for (int j=1;j<=18;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++){
        //scanf ("%d %d",&l,&r);
        l = read(),r = read();
        printf ("%d\n",query(l,r));
    }
    return 0;
}