ST表 是基于 倍增 思想的用于解决 RMQ问题 的一个算法
它可以在 \(O(nlog(n))\) 的时间预处理后, 用 \(O(1)\) 的时间 在线 回答 RMQ问题

蒟蒻代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const int N=1e5;
int n,q;
int a[N];
int f[N][20];

void ST_prework(){
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    int t=log(n)/log(2);
    for(int j=1;j<=t;j++)   // 枚举区间长度 (倍增)
        for(int i=1;i<=n-(1<<j)+1;i++)  // 枚举左端点位置
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);  // 前一半和后一半
}

int ST_query(int l,int r){
    int t=log(r-l+1)/log(2);    // l~r 内最长的 长度为2的幂 的区间
    return max(f[l][t],f[r-(1<<t)+1][t]);   // 两个 长度为2的幂 的区间覆盖了整个 l~r 区间
}

int main()
{
    ios::sync_with_stdio(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    ST_prework();
    while(q--){
        int x,y; cin>>x>>y;
        cout<<ST_query(x,y)<<endl;
    }

    return 0;
}

ST 表