专栏文章

st表学习

WWild_Of_The_World
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqmmd7b
此快照首次捕获于
2025/12/04 07:16
3 个月前
此快照最后确认于
2025/12/04 07:16
3 个月前
查看原文
P2880 [USACO07JAN] Balanced Lineup G
P1890 gcd区间
P3865 【模板】ST 表 && RMQ 问题
以上三题总结
对于st表需要注意的是各个位置的边界，+1-1
st表预处理标程：
CPP
lg[1]=0;
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[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]);
f[i][j]->[i,i+(1<<j)-1]
故预处理第二个for终点为i+(1<<j)-1<=n
注意第二段起点为i+(1<<(j-1))
查询：
CPP
int k=lg[r-l+1];
  max(f[l][k],f[r-(1<<k)+1][k])
r-l+1为区间长度
第二段起点x
x+(1<<k)-1=r -> x=r-(1<<k)+1

评论

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

正在加载评论...