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

作者：Li_阴宅 | 2024-07-08 16:29:37

踩

可重复贡献问题

引入

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

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

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

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

算法思想

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

这个时候我们就可以引出 $ST$ 算法了：

$ST$ 表基于倍增思想，可以做到 $O (n l o g n)$ 预处理，

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