RMQ算法讲解

时间：2015-11-24 14:48:57 阅读：245 评论：0 收藏：0 [点我收藏+]

RMQ算法

引入：

例1、题目描述

输入N个数和M次询问，每次询问一个区间[L,R],求第L个数到R个数之间的最大值。

第一种方法：大暴力之术。但是……时间复杂度最坏会达到 $O（NM）$，一半左右的点绝对爆T。

所以，引入了————RMQ！

RMQ：Range Maximum(Minimum) Query的缩写，顾名思义是用来求某个区间内的最大值或最小值，通常用在需要多次询问一些区间的最值的问题中。

RMQ的原理是动态规划

用A[1..N]表示一组数，F[I,J]表示从A[I]到A[I+2^J-1]这个范围内的最大值，也就是以A[I]为起点连续2^J个数的最大值，由于元素个数为2^J个，所以从中间平均分成两部分，每一部分的元素个数刚好为2^(J-1)个，如下图：

整个区间的最大值一定是左右两部分最大值的较大值，满足动态规划的最优原理

状态转移方程：

F[I,J]=max(F[I,J-1],F[I+2^(J-1),J-1])

边界条件为F[I,0]=A[I]

这样就可以在 $O(NlgN)$ 的时间复杂度内预处理F数组。

预处理F数组代码：

For i:=1 to n do f[I,0]:=a[i]

for j:=1 to trunc(ln(n)/ln(2)) do begin // 用到了换底公式，数学果然很重要

for i:=1 to n+1-1 shl j do

f[I,j]:=max(f[I,j-1],f[i+1 shl (j-1),j-1])

End;

对于询问[L,R],求出最大的x,满足2^x<=R-L+1,即x=trunc(ln(R-L+1)/ln(2))

[L,R]=[L,L+2^x-1] ∪[R+1-2^x,R]，两个子区间元素个数都是2^x个，如图

ANS(L,R)=max(F[L,x],F[R+1-2^x,x])

注意：在这里，RMQ在取最大最小值时，区间允许有重叠，但是求区间和的时候，坚决不能重叠，后果不用说。

询问操作代码：

Function query(L,R:longint):longint;

Var x:longint;

Begin

x:=trunc(ln(R-L+1)/ln(2));

exit(max(f[L,x],f[R+1-1 shl x,x]))

End;

该问题总时间复杂度为O(NlgN+M)，避免了暴力超时的问题，而且一般比线段树$ (M*lgN) $略快。

原文：http://www.cnblogs.com/zhtjtcz/p/4991371.html

踩

(0)

评论一句话评论（0）

分享档案

更多>