个人网站备案备注信息,erp系统教学,wordpress 删除 前缀,友情链接网自动收录本文参考【朝夕的ACM笔记】数据结构-ST表
在练习线段树的过程中经常会感叹代码怎么这么长啊啊啊懒标记怎么这么难传啊啊啊
于是在得知有一种代码量远小于线段树的算法时、、、#xff08;其实是因为做到了[SCOI2007] 降雨量
就是ST表啦~
在什么情况下可以用ST表代替线段树…本文参考【朝夕的ACM笔记】数据结构-ST表
在练习线段树的过程中经常会感叹代码怎么这么长啊啊啊懒标记怎么这么难传啊啊啊
于是在得知有一种代码量远小于线段树的算法时、、、其实是因为做到了[SCOI2007] 降雨量
就是ST表啦~
在什么情况下可以用ST表代替线段树呢
不需要区间修改的可重复贡献问题
不需要区间修改很好理解什么叫做可重复贡献呢
我们知道求一个数组的最大值比如说长度为10的数组我们可以先求前六个数的最大值再求后七个数的最大值最后求这两个最大值的最大值虽然这中间有重复的元素但是对最终的最大值结果不会有影响这就叫做可重复贡献问题。
但是如果我们要求一个数组中所有元素的和还是比如说长度为10的数组我们就不能用前六个元素的和加上后七个元素的和了这就叫做不可重复贡献问题。
常见的可重复贡献问题包括求区间最大/小值区间按位和/或区间gcd…
怎么构建ST表呢
ST表是一种基于倍增算法的数据结构
我们设f[i][j]表示区间 [ i , i 2 j − 1 ] [i, i 2^j - 1] [i,i2j−1] 的最大值因此f[i][0]表示的就是第 i 个元素本身了
由倍增思想区间 [ i , i 2 j − 1 ] [i, i 2^j - 1] [i,i2j−1] 可以被我们拆成两个长度为 2 j − 1 2^{j - 1} 2j−1 的子区间所以可以的到递推式 f [ i ] [ j ] m a x ( f [ i ] [ j − 1 ] , f [ i 2 j − 1 ] [ j − 1 ] ) f[i][j]max(f[i][j - 1], f[i 2^{j-1}][j-1]) f[i][j]max(f[i][j−1],f[i2j−1][j−1])因此先枚举 j j j再枚举 i i i就可以得到 f [ i ] [ j ] f[i][j] f[i][j] 的值了
怎么查询区间信息呢– RMQ算法
如果我们想知道 [ l , r ] [l, r] [l,r] 的最值我们可能会输出 f [ l ] [ x ] f[l][x] f[l][x], l 2 x − 1 r l2^x-1r l2x−1r这样解出x会发现 x l o g 2 ( r − l 1 ) xlog_2(r-l1) xlog2(r−l1)这样得到的 x 就不一定是个整数了向下取整的话可能会使区间有所损失
这时可重复贡献的性质就发挥作用了我们把要查询的区间 [ l , r ] [l,r] [l,r] 分成长度为 ⌊ x ⌋ \lfloor{x}\rfloor ⌊x⌋ 两部分一部分以 l 开头一部分以 r 结尾也就是 [ l , l 2 x − 1 ] [l, l2^x-1] [l,l2x−1] 和 [ r − 2 x 1 , r ] [r-2^x1,r] [r−2x1,r]只要找到这两个区间的最大值再取最大值就可以得到整个区间的最大值了
时间复杂度
预处理 O ( n l o g n ) O(nlogn) O(nlogn) 查询 O ( 1 ) O(1) O(1)
板子
#include bits/stdc.husing namespace std;int f[100005][21];
int logn[100005], n, m;void pre() // 预处理log 防止查询时T
{logn[1] 0, logn[2] 1;for (int i 3; i n; i)logn[i] logn[i / 2] 1;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n m;pre();// 输入数组本身for (int i 1; i n; i) cin f[i][0];for (int j 1; j 21; j) // 2的21次方满足两百万数据 数据变大上限也要变大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]); // 这里根据所求内容不同需要做相应修改while (m -- ){cin l r;// RMQ查询int lg logn[r - l 1];int ans max(f[l][lg], f[r - (1 lg) 1][lg]);cout ans \n;}
}
