当前位置:   article > 正文

数据结构——ST表_可重复贡献问题

可重复贡献问题

引入

ST表这种数据结构可以用来解决可重复贡献问题

 这里还不得不提一下什么是可重复贡献问题。

前置知识——可重复贡献问题

 可重复贡献问题是对于运算 o p t opt opt,运算的性质满足 x    o p t    x = x x\;opt\;x = x xoptx=x,则对应的区间询问就是一个可重复的贡献问题,例如:最大值满足 m a x ( x , x ) = x max(x,x)=x max(x,x)=x最大公因数满足 g c d ( x , x ) = x gcd(x,x)=x gcd(x,x)=x,因此 R M Q RMQ RMQ问题和 G C D GCD GCD问题就是一个可重复贡献的问题,但是例如区间和就不满足这个性质,因为在求解区间和的过程中采用的预处理区间会发生重叠,导致重叠部分被重复计算,因此对于 o p t opt opt操作还需要满足结合率才能够使用 S T ST ST表进行求解。

算法思想

 我们先来看一个例子:
  给定 n n n个数,有 m m m个询问,对于每个询问,你需要回答区间 [ l , r ] [l,r] [l,r]中的最大值。
 暴力的算法显然是 O ( n 2 ) O(n^2) O(n2)的,这个算法的效率比较低下。所以我们考虑优化。

 这个时候我们就可以引出 S T ST ST算法了:

S T ST ST表基于倍增思想,可以做到 O ( n l o g n ) O(nlogn) O(nlogn)预处理, O ( 1 ) O(1)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/799341
推荐阅读
相关标签
  

闽ICP备14008679号