赞
踩
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)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。