【模板】ST表

题目

洛谷P3865 ST表

题解

ST表适用于数据量较小,查询量较大的静态区间最值问题(RMQ问题)。

1.预处理

设f[i][j]为区间[i,i+2^j-1]内的最值,利用动态规划的思想,f[i][j]可以由f[][j-1]更新而来。

由于自带的log2()函数效率较低,所以需要自行递推,设lg2[n]表示log2(n)向下取整,则lg2[n]=lg2[n/2]+1。

2.询问

若要查询[l,r]内的最值,先要找到最大的x,使2^x<=r-l+1,然后取从左右端点l,r出发的两个长度为2^x的区间的最值的最值。

代码

Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月31日 下午7:40

【小白解析】
此题解题思路与树状数组1有些许相似,均是用2的幂表示区间长,总体并不难理解。
第19行的操作实则是将[i,i+2^j]分割成[i,i+2^(j-1)]与[i+2^(j-1),i+2^j]两个长度相同的区间,进而使用动态分配取得最大值。
lg2[]数组如博主所言,用于模拟(int)log2()的操作,实际作用是确定一个小于等于[l,r]区间长但大于其两倍的考察范围t,进而从l向右考察t个数字,从r向左考察t个数字,得出最大值。

cyx
cyx
Reply to  cyx
2020年9月1日 上午9:54

修正:
第19行的操作实则是将[i,i+2^j-1]分割成[i,i+2^(j-1)-1]与[i+2^(j-1),i+2^j-1]两个长度相同的区间,进而使用动态分配取得最大值。