RMQ问题

邢晗日

2023-12-01

一、基本定义

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

二、算法

（1）朴素

复杂度：O(n)-O(qn)

（2）线段树

复杂度：O(n)-O(qlogn)

参考文章：https://blog.csdn.net/weixin_43272781/article/details/83418431

（3）ST表

复杂度：O(nlogn)-O(q)

思路：ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k<=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。

d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。

参考文章： https://blog.csdn.net/weixin_43272781/article/details/88386252

（4）RMQ标准算法

复杂度：O(n)-O(q)

思路：首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。

建立笛卡尔树

数组A[0,N-1]的笛卡尔树C是这样一棵二叉树：当N=0，它是一棵空树，否则它的根节点是A中的一个最小元素A[i]（并以这个最小元素的下标i标记），而左右子树分别是A[0,i-1]和A[i+1,N-1]的一棵笛卡尔树。注意如果A中有相等的元素，则A的笛卡尔树不一定唯一，但在这里我们限定所用的最小元素为在数组中最先出现者，在此限制下笛卡尔树是唯一的。

容易看出，数组A在闭区间[l,r]上的最小值等同于笛卡尔树C中下标为l和r的两个顶点的最近公共祖先（LCA）的值。由此，RMQ问题可以转化为LCA问题。下面说明如何在O(n)时间内实现这一转化。

我们将要将A的元素依次插入笛卡尔树C。每次插入都可能使树的形态发生变化。为了在O(N)的时间内完成整个插入过程，考虑C的右链，即根结点、根结点的右儿子、根结点的右儿子的右儿子……组成的链。注意这些元素的下标和值都是递增的。下标最大，即将要插入的元素A[i]一定是新树右链的最后一个元素。原来的右链中，值比A[i]大的元素在新树中不再属于右链，这些元素组成的链成为A[i]的左子树的右链；原来右链中的其它元素加上A[i]组成了新的右链。初看起来，寻找分界点的最佳方法是O(logN)时间的二分查找；但是对于整个过程来说，O(NlogN)的时间复杂度不是最优的。关键在于一旦一个元素比A[i]大，它就从右链中被永久地移除了。如果按照从后到前的顺序判断一个元素是否大于A[i]，则每次插入的时间复杂度为O(k+1)，k为本次插入中移除的右链元素个数。因为每个元素最多进出右链各一次，所以整个过程的时间复杂度为O(N)。

用一个栈结构维护右链元素的下标，上述过程可以很容易地实现。（见下面代码部分）

转化为约束RMQ

为了将LCA问题转化为约束RMQ，我们注意到任意树中两个结点u和v的LCA就是在一次从树根开始的深度优先搜索中，在u和v之间（包括回溯时）到达的结点中层数最小的一个。为了利用这一事实，我们建立三个数组：

E[1,2*N-1]：在一次深度优先搜索（恰好是树的一次欧拉环游）中每一步到达的结点。

L[1,2*N-1]：E中对应结点在树中的层数。

H[1,N]：每个结点在E中某一次出现的下标（不妨设为第一次）。

则对任意u和v，不妨设H[u]≤H[v]（否则交换u和v），只要在L中找到[H[u],H[v]]中最小值的下标i，则E[i]就是u和v的LCA。注意到L满足约束RMQ的条件（相邻元素差的绝对值为1），这说明原来的LCA问题已经被转化为约束RMQ。转化过程显然能在O(N)时间内完成。

约束RMQ的解法

现在仍旧用A[0,N-1]表示问题中的数列，这里有|A[i]-A[i-1]|=1（i=1,2,...,N-1）成立。

将A分解为长度为l=[(log N)/2]的块。设A'[i]为第i块中的最小值，B[i]为该最小值的位置。A'[i]和B[i]的长度均为N/l，所以用ST算法处理A'数组的时空复杂度均为O(N/l*log(N/l))=O(N/logN*(logN-logl))=O(N)。预处理之后，对任意多连续的块进行的查询都能在O(1)时间内实现。余下的问题是如何进行块内查询。

注意到对任意一块中的块内查询的结果有影响的唯一因素是块内每相邻两个元素间的“升降关系”构成的序列。因为每两个元素之间的关系只有两种（“+1”、“-1”），而块的长度又只有l=[(log N)/2]，所以本质不同的块最多有2^I=O(sqrt N)种。对每种块中所有可能的块内查询预处理出答案的时空复杂度是O(sqrt N*l^2)=O(N)（这里的O(N)表示不超过线性时间）。预处理出所有块的“类型”，并用二进制数存储的时间复杂度是O(N)。

此后，每次查询可以分为两种情况：

1、块内查询，答案已经被预处理出，只要在数组中找到它即可。

2、块间查询，可以分解为2个块内查询，和一个A'上的RMQ，三者的时间复杂度都是O(1)。

综上，我们给出了一个预处理时间为O(n)，查询时间为O(1)的在线RMQ算法。