专栏文章

ST 表 SPARSE TABLE

HHYLW
科技·工程参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqy7s8i
此快照首次捕获于
2025/12/04 12:41
3 个月前
此快照最后确认于
2025/12/04 12:41
3 个月前
查看原文

前言

第一服役期都要结束了还写什么博客
ST 表是一种基于预处理、倍增、分块的数据结构，主要解决 RMQ 问题，并且就离线询问来讲（它也只能离线询问）是相当高效的，当然预处理的可能要稍微花点与其他数据结构同级别的时间，不太支持修改，与最值强联系的性质才能用。

正文

0x01.ST 表基础

理论基础

有一种东西，叫做二的次幂，还有一种东西，叫做对数，对于很大的数量，比如说 10910^9，取一个以 22 为底的对数（取整）就可以得到极小的 3131，降了 77 个数量级。
还有最值，有一种性质是
x=max⁡({A},{B},{C})⇒x=max⁡({A}∪{C},{B}∪{C})x=\max(\{A\},\{B\},\{C\})\Rightarrow x=\max(\{A\}\cup\{C\},\{B\}\cup\{C\} )
x=min⁡({A},{B},{C})⇒x=min⁡({A}∪{C},{B}∪{C})x=\min(\{A\},\{B\},\{C\})\Rightarrow x=\min(\{A\}\cup\{C\},\{B\}\cup\{C\} )
也就是对于一段整数序列的区间 [l,r][l,r] 内，有 ∀⌈r−l+12⌉≤z≤r−l+1,z∈Z\forall\lceil\frac{r-l+1}{2}\rceil\leq z\leq r-l+1,z\in Z 满足 max⁡[l,r]=max⁡(max⁡[l,l+z−1],max⁡[r−z+1,r])\max[l,r]=\max(\max[l,l+z-1],\max[r-z+1,r])。
那么对于一段长度为 nn 序列 {ai}\{a_i\} ，我们可以对于每个位置记录 log⁡2n\log_2n 个 sti,jst_{i,j} 表示区间 [i,i+2j−1][i,i+2^j-1] 内的 max⁡ai\max a_i 或者 min⁡ai\min a_i，于是对于任意的离线询问 [l,r][l,r] 的最值，答案就是
max⁡(stl,t,str−2t+1,t)ormin⁡(stl,t,str−2t+1,t)(t=⌊log⁡2(r−l+1)⌋)\max(st_{l,t},st_{r-2^t+1,t}) \text{or}\min(st_{l,t},st_{r-2^t+1,t})(t=\lfloor\log_2(r-l+1)\rfloor)
具体的，就可以在 nlog⁡nn\log n 的时间复杂度内预处理，然后 O(1)O(1) 离线查询区间最值哩。

代码实现

假设给定一个序列，离线求区间最大值。
首先，为了避免 log⁡2x\log_2 x 带来的较大常数，我们一般预处理出 log⁡2x,1≤x≤n\log_2x,1\leq x\leq n，时间复杂度 O(n)O(n)。
然后为了得到 sti,jst_{i,j}，因为 sti,j=max⁡(sti,j−1,sti+2j,j−1)st_{i,j}=\max(st_{i,j-1},st_{i+2^j,j-1})，所以按照区间以二的次幂增大的方式更新每个位置的 sti,jst_{i,j}，有一个 O(n)O(n) 的对 sti,0st_{i,0} 的预处理，然后时间复杂度 O(nlog⁡n)O(n\log n)。
最后，在询问时，先处理出区间长度对应的 log⁡\log 整数，然后借助理论基础里的式子就可以 O(1)O(1) 得到想要的答案。
max⁡[l,r]=max⁡(stl,t,str−2t+1,t)ormin⁡(stl,t,str−2t+1,t)(t=⌊log⁡2(r−l+1)⌋)\max[l,r]=\max(st_{l,t},st_{r-2^t+1,t}) \text{or}\min(st_{l,t},st_{r-2^t+1,t})(t=\lfloor\log_2(r-l+1)\rfloor)
以下是样例代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,m;
int a[N];

int st[N][12];
int logn[N];

void init(){
	logn[1]=0;
	for(int i=2;i<=n;i++)	logn[i]=logn[i/2]+1;//取对数
	
	for(int j=1;j<=logn[n];j++)//枚举区间长度
		for(int i=1;i+(1<<j)-1<=n;i++)//枚举位置，更新st数组
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

int ask(int l,int r){//O(1)查询
	if(l>r)	return 0;
	int t=logn[r-l+1];
	return max(st[l][t],st[r-(1<<t)+1][t]);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),st[i][0]=a[i];//输入+预处理
	init();
	for(int i=1,l,r;i<=m;i++){
		scanf("%d%d",&l,&r);
		printf("%d\n",ask(l,r));
	}
	return 0;
}
贝斯特的优化：有一种东西，叫做地址访问优化，也就是对于数组来讲，维数小的放前面，会比维数大的放前面访问更快，这种东西对于极大的数组来讲，优化相当之大，在状态压缩等应用中也有十足的表现。

贝蒂的练习

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...