RMQ
简介¶
RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。
在笔者接下来的描述中,默认初始数组大小为
在笔者接下来的描述中,默认时间复杂度标记方式为
单调栈¶
由于 OI Wiki 中已有此部分的描述,本文仅给出 链接。这部分不再展开。
时间复杂度
空间复杂度
ST 表¶
由于 OI Wiki 中已有此部分的描述,本文仅给出 链接。这部分不再展开。
时间复杂度
空间复杂度
线段树¶
由于 OI Wiki 中已有此部分的描述,本文仅给出 链接。这部分不再展开。
时间复杂度
空间复杂度
Four Russian¶
Four russian 是一个由四位俄罗斯籍的计算机科学家提出来的基于 ST 表的算法。
在 ST 表的基础上 Four russian 算法对其做出的改进是序列分块。
具体来说,我们将原数组——我们将其称之为数组 A——每
对于每一块我们预处理出来块内元素的最小值,建立一个长度为
同时,我们对于数组 A 的每一个零散块也建立一个 ST 表。
询问的时候,我们可以将询问区间划分为不超过 1 个数组 B 上的连续块区间和不超过 2 个数组 A 上的整块内的连续区间。显然这些问题我们通过 ST 表上的区间查询解决。
在
时间复杂度
空间复杂度
当然询问由于要跑三个 ST 表,该实现方法的常数较大。
一些小小的算法改进
我们发现,在询问的两个端点在数组 A 中属于不同的块的时候,数组 A 中块内的询问是关于每一块前缀或者后缀的询问。
显然这些询问可以通过预处理答案在
这样子我们只需要在询问的时候进行至多一次 ST 表上的查询操作了。
一些玄学的算法改进
由于 Four russian 算法以 ST 表为基础,而算法竞赛一般没有非常高的时间复杂度要求,所以 Four russian 算法一般都可以被 ST 表代替,在算法竞赛中并不实用。这里提供一种在算法竞赛中更加实用的 Four russian 改进算法。
我们将块大小设为
查询时,对于左右端点不在同一块内的询问,我们可以直接
而对于左右端点在同一块内的询问,我们可以暴力求出两点之间的 RMQ,时间复杂度为
而在算法竞赛中,我们并不用非常担心出题人卡掉这种算法,因为我们可以通过在
这是一种期望时间复杂度达到下界,并且代码实现难度和算法常数均较小的算法,因此在算法竞赛中比较实用。
以上做法参考了 P3793 由乃救爷爷 中的题解。
笛卡尔树在 RMQ 上的应用¶
不了解笛卡尔树的朋友请移步 笛卡尔树。
我们发现,原序列上两个点之间的 min/max,等于笛卡尔树上两个点的 LCA 的权值。
这也说明,我们现在需要去解决的是如何
树上 LCA 在 LCA 部分已经有描述,这里不再展开。
这里我们需要采用的是基于 RMQ 的树上 LCA 算法。
可能会有同学会问:为什么我们在绕了一圈之后,又回到了 RMQ 问题呢?
别着急,我们来找一找这个 RMQ 问题的特殊性质:
因为树的 dfs 序列的相邻两个节点互为父子关系,也就是说相邻两个节点深度差为
根据这个特性我们就可以改进 Four Russian 算法了。
由于 Four russian 算法的瓶颈在于块内 RMQ 问题,我们重点去讨论块内 RMQ 问题的优化。
由于相邻两个数字的差值为
这启示我们可以预处理所有不超过
在预处理的时候我们需要去预处理同一块内相邻两个数字之间的差,并且使用二进制将其表示出来。
在询问的时候我们找到询问区间对应的二进制表示,查表得出答案。
这样子 Four russian 预处理的时间复杂度就被优化到了
结合笛卡尔树部分我们就可以实现
代码和例题由于在 LCA 部分已经给出 链接,这里不再赘述。
当然由于转化步数较多,
如果数据随机,则我们还可以暴力在笛卡尔树上查找。此时的时间复杂度为期望
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用