ST表
cpp
struct SparseTable{
vector<vector<int>> st;
int n;
void init(int n,vector<int> &a){
this->n=n;
st=vector<vector<int>>(n+1,vector<int>(28,INF));
for(int i=1;i<=n;i++)st[i][0]=a[i];
for(int j=1;1<<j<=n;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=__lg(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
};