ST表总结

ST表是用来解决可重复贡献的数据结构。

原理

基于倍增的思想。

RMQ模板

void init(int n){
	for(int i=2;i<N;i++)	//预处理log函数,实现O(1)询问
		b[i]=b[i/2]+1;
	for(int j=1;j<=b[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);
	init(n);
	while(q--){
		int l,r;scanf("%d%d",&l,&r);
		int x=b[r-l+1];
		printf("%d\n",max(f[l][x],f[r-(1<<x)+1][x]));
	}
	return 0;
}

ST表的应用

区间最值、区间GCD、区间按位与、区间按位或。

优缺点

不支持修改，维护信息有限。

二维ST表

• 一般是维护正方形的最值

令 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示以 ( i , j ) (i,j) (i,j)为左上角边长为 2 k 2^k 2k的矩形的最大值。

有递推式： f i , j , k = max ⁡ { f i , j , k − 1 , f i + 2 k − 1 , j , k − 1 , f i , j + 2 k − 1 , k − 1 , f i + 2 k − 1 , j + 2 k − 1 , k − 1 } \large f_{i,j,k}=\max\{f_{i,j,k-1},f_{i+2^{k-1},j,k-1},f_{i,j+2^{k-1},k-1},f_{i+2^{k-1},j+2^{k-1},k-1}\} fi,j,k​=max{fi,j,k−1​,fi+2k−1,j,k−1​,fi,j+2k−1,k−1​,fi+2k−1,j+2k−1,k−1​}

void init(){
	for(int k=1;k<=g;k++)
		for(int x=1;x+(1<<k)-1<=A;x++)
			for(int y=1;y+(1<<k)-1<=B;y++)
		{
	f[x][y][1]=max({f[x][y][1],f[x+(1<<k-1)][y+(1<<k-1)][1],f[x+(1<<k-1)][y][1],f[x][y+(1<<k-1)][1]});
	f[x][y][0]=min({f[x][y][0],f[x+(1<<k-1)][y+(1<<k-1)][0],f[x+(1<<k-1)][y][0],f[x][y+(1<<k-1)][0]});
		//printf("%d %d\n",f[x][y][1],f[x][y][0]);
		}
}

若题目求固定边长 n n n的最值，则可以省去第三维，递推到 2 k + 1 ≥ n 2^{k+1}\ge n 2k+1≥n即可。