【模板】ST 表 Sparse Table

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]);}
};

原文地址：http://www.cnblogs.com/caijianhong/p/16863430.html