st表

st表。


\(O(1)\)时间查询

/*
倍增建
*/
void build(){
	for(int i=1;i<=n;i++)
		st[i][0]=__[i];
	for(int j=1;j<=logn;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]);
}
/*
查询就是找一个2的几次方k小于l到r的长度，然后min一下两段
*/
int query(int l,int r){
	int k=0;
	while(1<<k+1<=r-l+1) k++;
	return min(st[l][k],st[r-(1<<k)+1][k]);
}