RMQ问题的四种解法

时间:2021-04-12 00:38:47

什么是RMQ问题:

   RMQ (Range Minimum/Maximum Query):对于长度为n的数组A,回答若干询问RMQ(A,i,j)(i,j<=n-1),返回数组A中下标在i,j范围内的最小(大)值,也就是说,RMQ问题是指求区间最值的问题。


1.暴力法最简单的方法,就是遍历数组直接搜索,但是这种方式时间复杂度是O(n)。对于数组长度较大,性能要求高的场景不适用。一般用这个算法就等着TLE,时间复杂度最坏O(Q*N),也不一定超时,签到题可能就直接让你过了。


2.ST(Sparse Table)算法

ST算法是一种更加高效的算法,基于动态规划的思想,以O(nlogn)的预处理代价,换取O(1)的查询时性能。但是,是离线的,也就是说每次修改都是O(nlogn)复杂度,那么用在带修的题目上就显得捉襟见肘了。


3.树状数组


从下向上更新,sum改为max/min即可,但是局限性比较大吧,很少看见用树状数组求最值的题解。


4.线段树是基于分治的思想来实现的,建立是o(nlogn)查询为O(logN),那么也就是说这个可以进行修改,单点修改维护也是logN。


分析也就是说,我们可以抛开1/3不谈,当题目是离线的时侯使用ST算法更快,当题目是在线的时候直接使用线段树维护即可,好像还有一种万能的莫队,不在考虑范围之内。