ST 表：静态区间最大值

算法理解

st[i][j] 表示从 i 开始、长度为 2^j 的区间最大值。查询时用两个长度相同、允许重叠的块覆盖目标区间。最大值、最小值、GCD 这类幂等运算都适用。

• 复杂度：预处理 O(n log n)，每次查询 O(1)。
• 注意：只适合静态数组；原模板内层边界应使用 n，不能写成数组上限 N。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=1e9+7;
const int N=1e5+10;
const int M=22;
#define endl '\n'
#define lowbit(x) (x&(-x))
#define vc vector<int>

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m;
int st[N][M];
int a[N];
void pre()
{
    for (int i=1;i<=n;i++) st[i][0]=a[i];
    for (int j=1;j<M;j++)
    {
        for (int i=1;i+(1<<j)-1<=N;i++)
        {
            st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l,int r)
{
    int ans=-1e9;
    int len=__lg(r-l+1);
    ans=max(st[l][len],st[r-(1<<len)+1][len]);
    return ans;
}
void solve()
{
    n = read(), m = read();
    for (int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    pre();
    while(m--)
    {
        int l = read();
        int r = read();
        cout<<query(l,r)<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
//  cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

‍