最后一题就是考试前一周讲过的 （虽然我忘了）

附上指导和代码：

ST表详细指导：

数据结构定义：

st[i][j]：表示从位置i开始，长度为2^j的区间的最小值

log_[i]：预处理存储log2(i)的整数值

预处理log2值：

利用递推公式：log2(i) = log2(i/2) + 1

构建ST表：

初始化：st[i][0] = a[i]（长度为1的区间）

递推：st[i][j] = min(st[i][j-1], st[i+2^(j-1)][j-1])

即将区间[i, i+2^j-1]分成两个长度为2^(j-1)的子区间

查询操作：

计算k = log2(R-L+1)

查询结果 = min(st[L][k], st[R-2^k+1][k])

这样确保两个区间[L, L+2^k-1]和[R-2^k+1, R]覆盖了整个查询区间[L,R]

时间复杂度分析：

预处理：O(n log n)

每次查询：O(1)

总体：O(n log n + q)，对于n,q≤1e5完全可行

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int LOG=17;
int n,q,a[N];
int st[N][LOG];
int log_[N];
void prelog(){
    log_[1]=0;
    for(int i=2;i<=n;i++){
        log_[i]=log_[i/2]+1;
    }
}
void build(){
    for(int i=1;i<=n;i++){
        st[i][0]=a[i];
    }
    for(int j=1;j<LOG;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int L,int R){
    int k=log_[R-L+1];
    return min(st[L][k],st[R-(1<<k)+1][k]);
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    prelog();
    build();
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    return 0;
}