posted on 2022-07-22 19:15:58 | under 模板 | source
template<int N,class T=int,int logN=20> struct STable{
int tot,lg[N+10];T f[logN+1][N+10];
STable():tot(0){lg[0]=-1;for(int i=1;i<=N;i++) lg[i]=lg[i>>1]+1;}
void insert(T x){f[0][++tot]=x;for(int j=0,i=tot-1;i>=1;i-=1<<++j) f[j+1][i]=min(f[j][i],f[j][i+(1<<j)]);}
T query(int l,int r){int k=lg[r-l+1];return min(f[k][l],f[k][r-(1<<k)+1]);}
};