RMQ（ST表）

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;
int N, M, a[100009], l, r, st[100009][20];
inline int read()
{
    int s=0, w=1; char ch=getchar();
    while( ch<'0' || ch>'9' ){ if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0' && ch<='9'){ s=s*10+ch-'0';    ch=getchar(); }
    return s*w;
}
void pre()                                      //预处理求st表 
{
    for(register int i=1; i<=N; i++) st[i][0]=a[i];
    for(int k=1; (1<<k)<=N; k++)
        for(register int i=1; i<=N; i++)
        {
            if(i+(1<<k)-1>N) break;
            st[i][k]=max(st[i][k-1], st[i+(1<<(k-1))][k-1]);
        }
}
int maxf(int l, int r)                          //区间划分与求值 
{
    if(l==r) return st[l][0];
    int t=log(r-l)/log(2);                      //注意在Linux下log计算可能存在的潜在问题 
    return max(st[l][t], st[r-(1<<t)+1][t]);
}
int main()
{
    N=read(), M=read();
    for(register int i=1; i<=N; i++) a[i]=read();
    pre();
    for(register int i=1; i<=M; i++) l=read(), r=read(), printf("%d\n", maxf(l, r));
    return 0;
}

RMQ（ST表）

原文：https://www.cnblogs.com/lfyzoi/p/10565026.html