网站框架规划,为什么网站开发成本高,wordpress 主题文件,电子商务与网络营销教案文章目录 前言可重复贡献问题ST表的定义ST表的存储结构ST表的预处理预处理的实现 ST表的区间查询对于k的获取区间查询的实现 OJ链接 前言 对于查询区间最值的方法#xff0c;我们常用的就是线段树#xff0c;树状数组#xff0c;单调队列#xff0c;而树状数组更适合用于快… 文章目录 前言可重复贡献问题ST表的定义ST表的存储结构ST表的预处理预处理的实现 ST表的区间查询对于k的获取区间查询的实现 OJ链接 前言 对于查询区间最值的方法我们常用的就是线段树树状数组单调队列而树状数组更适合用于快速求区间和而单调队列维护区间最值只在特殊情况下适用最无解的线段树空间开销大而且有一定的代码量它在动态维护区间最值上基本上可以说是最优解但是如果是离线询问的话本文将介绍的ST表代码量远小于线段树而且还能达到不错的时间复杂度。 可重复贡献问题
可重复贡献问题是指对于运算opt 任意操作数x都满足x opt x x。例如max(x , x) x , gcd(x , x) x因此RMQ(区间最值查询)和区间gcd问题也是可重复贡献问题。
ST表的定义
ST表Sparse Table稀疏表是一种适用于符合结合律且可重复贡献的信息查询的数据结构如区间最大值、最小值、最大公因数最小公倍数按位或按位与等。在处理RMQ查询区间最值问题时通过倍增思想我们可以以O(nlogn)预处理从而实现O(1)查询。
ST表的存储结构
ST表的存储结构非常简单就是一个二维数组f , 其中f[i][j]代表以第i个数为起点长度为2^j次方的区间内的最值。
我们接下来均以最大值做讨论。
#define N 100010
int f[N][20];ST表的预处理
我们如何去获取这样一个ST表呢
对于一个大问题我们可以将其拆解为若干个小问题利用其可重复贡献性来逐步得到我们问题的答案。
ST表以倍增法做递推来预处理ST表其实是一种自下而上的动态规划。
对于一个区间最大值而言显然等于两个等长子区间最大值的最大值。那么根据我们f[i][j]的定义可有如下递推公式 f [ i ] [ j ] m a x ( f [ i ] [ j − 1 ] , f [ 1 ( i 2 j − 1 ] [ j − 1 ] ) f[i][j] max(f[i][j-1] , f[1(i2^{j-1}][j-1]) f[i][j]max(f[i][j−1],f[1(i2j−1][j−1]) 那么我们只需要固定区间长度然后枚举起点自下而上进行动态规划即可由于区间长度每次倍增所以不难得出我们的时间复杂度为O(nlogn) 预处理的实现
实现流程 目标序列arr长度为n下标从1开始初始化f[i][0]为arr[i]枚举长度j然后枚举起点i进行状态转移注意区间边界和位运算优先级 for (int i 1; i n; i)f[i][0] arr[i];for (int j 1; j 20; j)for (int i 1; i (1 j) - 1 n; i)f[i][j] min(f[i][j - 1], f[i (1 (j - 1))][j - 1]);ST表的区间查询
我们ST表能够实现对于任意区间[l , r](1 l,r n)内的最值查询那么是如何实现的呢
我们已经知道了区间最值可以有子区间最值转移而来那么对于区间[l , r]我们一定可以找到k使得 2 k ≤ log 2 ( r − l 1 ) 2 k 1 2^{k}\le\log_{2}{(r - l 1)}2^{k1} 2k≤log2(r−l1)2k1 那么我们可以得到分别以l为左端点和以r为右端点的两个长度为2^k的区间这两个区间的最值的最值就是我们[l , r]区间内的最值。 q u e r y ( l , r ) m a x ( f [ l ] [ k ] , f [ r − 2 k 1 ] [ k ] ) query(l , r) max(f[l][k],f[r-2^{k}1][k]) query(l,r)max(f[l][k],f[r−2k1][k])
对于k的获取
k显然就是log2 (r - l 1)向下取整这里我们有两种方案获取log2值
F1 递推预处理
观察下2^n求和公式很容易想明白这个递推我们O(n)预处理分摊每次取log2为O(1)
//int Log2[N]{0};
for (int i 2; i n; i)Log2[i] Log2[i / 2] 1;F2 直接用cmath里的log2
区间查询的实现 for (int i 0; i n; i){//l read(), r read();cin l r;int k log2(r - l 1);cout min(f[l][k], f[r - (1 k) 1][k]) ;//write(min(f[l][k], f[r - (1 k) 1][k])), putchar( );}到此ST表的原理及实现就结束了代码量非常少在处理离线查询跟线段树的代码量比起来显然这个出错率更低。
我们上面都是以最大值为例进行实现的在实际应用中只要是满足结合律且可重复贡献的信息查询都在ST表的解决范围内因为ST表能够对两个交集非空的子区间进行信息合并这也就是重复贡献的精妙之处。
OJ链接
A几个水题爽一下
找几个板子题练练手
P3865 【模板】ST 表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P1816 忠诚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
[P2880 USACO07JAN] Balanced Lineup G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
