Skip to content

RMQ 问题（区间最值问题）

介绍

RMQ (Range Minimum/Maximum Query) 问题是指：

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

时间复杂度: O(N)~O(logN)

主要方法

  1. 朴素（即搜索）， O(n)~O(qn) ，online。
  2. 线段树， O(n)~O(qlogn) ，online。
  3. ST （实质是动态规划）， O(nlogn)~O(q) ，online。
  4. RMQ 标准算法：先规约成 LCA (Lowest Common Ancestor) ，再规约成约束 RMQ ， O(n)-O(q) ，online。

ST 算法

代码：Code

一、简介

ST 算法 (Sparse Table) 。

以求最大值为例，设 f[i,j] 表示 \([i,i+2^j-1]\) 这个区间内的最大值，那么在询问到 \([a,b]\) 区间的最大值时答案就是 max(f[a,k], f[b-2^k+1,k]) ，其中 k 是满足 \(2^k\le b-a+1\) （即长度）的最大的 k ，即 \(k=[\frac{\ln(b-a+1)}{\ln(2)}]\) 。

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

二、详细步骤

来看一下 ST 算法是怎么实现的（以最大值为例）：

首先是预处理，用一个 DP 解决。设 a 是要求区间最值的数列， f[i,j] 表示从第 \(i\) 个数起连续 \(2^j\) 个数中的最大值。

例如数列 3 2 4 5 6 8 1 2 9 7

f[1,0] 表示第 \(1\) 个数起，长度为 \(2^0=1\) 的最大值，其实就是 3 这个数。

f[1,1]=3 ， f[1,2]=5 ， f[1,3]=8 ， f[2,0]=2 ， f[2,1]=4 ……

从这里可以看出 f[i,0] 其实就等于 a[i] 。这样， DP 的状态、初值都已经有了，剩下的就是状态转移方程。

我们把 f[i,j] \((j\ge 1)\) 平均分成两段（因为 \(j\ge 1\)时， f[i,j] 一定是偶数个数字），从 \(i\) 到 \(i+2^{j-1}-1\) 为一段， \(i+2^{j-1}\) 到 \(i+2^j-1\) 为一段（长度都为 \(2^{j-1}\) ）。

用上例说明，当 i=1 , j=3 时就是 3,2,4,5 和 6,8,1,2 这两段。 f[i,j] 就是这两段的最大值中的最大值。

于是我们得到了动规方程 f[i,j]=max(f[i,j-1],f[i+2^(j-1),j-1]) 。

接下来是得出最值，也许你想不到计算出 f 有什么用处，一般要想计算 max 还是要 O(logn) ，甚至 O(n) 。但有一个很好的办法，做到了 O(1) 。

还是分开来。如在上例中我们要求区间 [2,8] 的最大值，就要把它分成 [2,5] 和 [5,8] 两个区间，因为这两个区间的最大值我们可以直接由 f[2,2] 和 f[5,2] 得到。

扩展到一般情况，就是把区间 \([l,r]\) 分成两个长度为 \(2^n\) 的区间（保证有 f 对应）。直接给出表达式：

    k=floor(ln(r-l+1)/ln(2));
    ans=max(f[l][k],f[r-2^k+1][k]);

这样就计算了从 \(l\) 开始，长度为 \(2^k\) 的区间和从 \(r-2^k+1\) 开始长度为 \(2^k\) 的区间的最大值，二者中的较大者就是整个区间 \([l,r]\) 上的最大值。

三、算法流程

  1. 预处理
    实质：动态规划
    设 a[1...n] ，设 f[i][j] 表示从 a[i] 到 a[i+2j-1] 最大值，共 \(2^j\) 个。
    由于共 \(2^j\) 个，可将其分成两份，分别是 f[i][j-1] 和 f[i+2^j-1][j-1] 。
    状态转移方程：
    f[i][j]=max(f[i][j-1],f[i+2^j-1][j-1])
    边界条件为 f[i][0]=a[i]
    时间复杂度 O(nlogn)

  2. 询问
    若我们询问区间 \([l,r]\) 的最大值，则先求出最大的 \(x\) 满足 \(2^x\le r-l+1\) ，那么区间 \([l,r]=[l,l+2^x-1]\cup [r-2^x+1,r]\)
    那么 \([l,r]\) 的最大值为 max(f[l][x],f[r-2^x+1][x])，可在 O(1) 内算出。
    虽然有交集，但并不影响，这就是 ST 算法只适用于求区间最值的原因。
    对于求区间 \([x,y]\)
    K=log2(y-x+1)
    ans=max(f[x][k],f[y-2^k+1][k])

  3. 技巧
    因为 cmath 库中的 log2() 函数效率不高，所以除了调用 log2() 函数外，通常还会使用 O(N) 递推预处理出 \(1\ldots N\) 这 \(N\) 种区间长度各自对应的 \(k\) 值。具体地，设 log[d] 表示 \(\log_2(d)\) 向下取整，则 log[d]=log[d/2]+1 。

RMQ 标准算法

一、简介

首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为 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,\ldots,N-1)\)成立。

将 A 分解为长度为 \(l=[(\log_2{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_2{N})/2]\) ，所以本质不同的块最多有 \(2^l=O(\sqrt{N})\) 种。对每种块中所有可能的块内查询预处理出答案的时空复杂度是 \(O(\sqrt{N\times l^2})=O(N)\) （注：这个式子不一定正确，有空记得确认一下）（这里的 \(O(N)\) 表示不超过线性时间）。预处理出所有块的“类型”，并用二进制数存储的时间复杂度是 O(N) 。

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

  1. 块内查询，答案已经被预处理出，只要在数组中找到它即可。
  2. 块间查询，可以分解为 \(2\) 个块内查询，和一个 A' 上的 RMQ ，三者的时间复杂度都是 O(1) 。

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

核心代码：

//TODO

注：部分资料来源于百度百科

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.