专栏文章

浅谈——RMQ问题

cchenzefan
算法·理论参与者 8已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
2 份
快照标识符
@mk9zdf97
此快照首次捕获于
2026/01/12 01:01
上个月
此快照最后确认于
2026/02/19 01:20
12 小时前
查看原文
RMQ\text{RMQ} 是 RangeMinimum/MaximumQuery\tt{Range Minimum/Maximum Query} 的缩写，表示区间最大最小值。

step1.倍增法（ST 表）

最朴素的方法。时间复杂度为 O(nlog⁡n+q)O(n \log n+q)。
预处理时间复杂度 O(nlog⁡n)O(n \log n)，每次查询 O(1)O(1)。
以求最大值为例。

定义

定义 fi,jf_{i,j} 表示区间 [i,i+2j−1][i,i+2^j-1] 的区间最大值。

初始化

fi,0f_{i,0} 表示区间 [i,i][i,i] 的结果，即 aia_i。故有 fi,0=aif_{i,0}=a_i。

转移

由于区间最大值支持合并，则显然区间 [l,r][l,r] 可以由 [l,mid][l,mid] 和 [mid+1,r][mid+1,r] 合并而来。mid=l+r2mid=\frac{l+r}{2}。回归定义，可以得出转移方程：
fi,j=max⁡{fi,j−1,fi+2j−1,j−1}f_{i,j}=\max\{f_{i,j-1},f_{i+2^{j-1},j-1}\}
预处理复杂度为 O(nlog⁡n)O(n \log n)。
CPP
for(int j=1;j<=log2(n);j++)
    for(int i=1;i+(1<<j)-1<=n;i++)
       f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);

询问

目前已经求出了 ff 数组。
询问区间 [l,r][l,r] 的最大值。考虑用 ff 去覆盖应有区间。
显然我们可以令 k=log⁡2{r−l+1}k=\log_2\{r-l+1\}。
那么答案就是 max⁡{fi,k,fr−2k+1,k}\max\{f_{i,k},f_{r-2^k+1,k}\}。
思考一下，其实就是覆盖左边和右边。中间有重复没关系。全部覆盖就行。
CPP
int k=log2(r-l+1);
printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
每次询问复杂度为 O(1)O(1)。
优点：易懂。

step2.离线单调栈

复杂度 O(qlog⁡q+qlog⁡n)O(q \log q+q \log n)。
排序复杂度 O(qlog⁡q)O(q \log q)，每个询问二分 O(log⁡n)O(\log n)。

方法

离线下来所有询问，按右端点 rr 排序。然后每次在序列 aa 上找到当前询问的右端点 rr 处，并把找到的元素压入到单调栈中。这样，对于每个询问时，单调栈中存储的值满足在 aa 中的位置 ≤r\le r。只需找到序列中第一个 ≥l\ge l 的值。显然可以二分来找。
优点：空间复杂度 O(n)O(n)。
时间复杂度 O(qlog⁡q+qlog⁡n)O(q \log q +q\log n)。
CPP
sort(query+1,query+m+1,cmp);
for(int i=1,j=1;i<=m;i++){
    while(j<=query[i].r){
        while(cnt&&a[j]>a[st[cnt]]) cnt--;
        st[++cnt]=j++;
    }
    int pos=lower_bound(st+1,st+cnt+1,query[i].l)-st;
    ans[query[i].id]=a[st[pos]];
}

step3.线段树/树状数组

很模板的线段树。维护区间最大值。
建树 O(n)O(n)，每次查询 O(log⁡n)O(\log n)，总共为 O(n+qlog⁡n)O(n+q\log n)。
优点：模板且没有思维含量。
那么树状数组也能做。 似乎没必要。

step4.四毛子前置算法（分块）

四毛子算法原名 FourRussian\tt{Four Russian}。这里分析前置算法——分块。

方法

考虑将原序列每 BB 个分进一个块，则共有 nB\frac{n}{B} 个块。
每次询问情况可分为以下几种：
  • 块内：直接遍历找最大值。
  • 相邻块中：前面块的一段后缀的贡献和后面块的一段前缀的贡献取并。
  • 间隔很多块：考虑第一个块后缀和最后一个块的前缀，中间的整块直接用 ST 表 O(1)O(1) 查询。
梳理一下就是：
  • 对于每一个块预处理前缀最大值和后缀最大值。复杂度 O(nB×B)=O(n)O(\frac{n}{B}\times B)=O(n)。
  • 对于每个块总体贡献建立 ST 表，那么也就是 nB\frac{n}{B} 个块之间的 ST 表，时间复杂度为 O(nBlog⁡nB)O(\frac{n}{B}\log\frac{n}{B})。
再发掘一下，发现每次询问最坏情况为同块时，需暴力扫一遍，则时间复杂度为 O(qB)O(qB)。其余情况直接可以 O(1)O(1) 解决。考虑如何优化？

优化 11：块内 ST 表

我们是否可以在每个块内建立 ST 表呢？
答案显然，故时间复杂度为 O(n+nBlog⁡nB+nB×Blog⁡B+q)=O(n+nBlog⁡nB+nlog⁡B+q)O(n+\frac{n}{B}\log\frac{n}{B}+\frac{n}{B}\times B\log B+q)=O(n+\frac{n}{B}\log\frac{n}{B}+n \log B+q)。
考虑取 B=log⁡nB=\log n，得到时空复杂度都近似为 O(nlog⁡log⁡n+q)O(n \log \log n+q)。
优点：实现简单。

优化 22：±1RMQ\pm1\text{RMQ} 问题

继续优化同块的情况。
oi_wiki 对于笛卡尔树的解释。
不难发现，通过构建原序列的笛卡尔树，即可把原本的 RMQ\text{RMQ} 问题转化成了树上 LCA\text{LCA} 问题，继续转换，就变成了 ±1RMQ\pm1\text{RMQ} 问题。可以预处理 O(n)O(n)，每次查询 O(1)O(1)，共 O(n+q)O(n+q) 的时间内解决。
±1RMQ\pm1\text{RMQ} 问题定义为相邻两个值的差为 ±1\pm1。即 ∀i∈{x∣1≤x<n},∣ai−ai+1∣=1\forall i \in \{x|1 \le x < n\},|a_i-a_{i+1}|=1。
引用一段文字（摘自 OI_wiki，进行了格式优化）：
由于 FourRussian\tt{Four Russian} 算法的瓶颈在于块内 RMQ\text{RMQ} 问题，我们重点去讨论块内 RMQ\text{RMQ} 问题的优化。
由于相邻两个数字的差值为 ±1\pm1，所以在固定左端点数字时 长度不超过 log⁡n\log n 的右侧序列种类数为 ∑i=1log⁡n2i−1\displaystyle\sum_{i=1}^{\log n} 2^{i-1}，而这个式子显然不超过 nn。
这启示我们可以预处理所有不超过 nn 种情况的最小值-第一个元素的值。
在预处理的时候我们需要去预处理同一块内相邻两个数字之间的差，并且使用二进制将其表示出来。
在询问的时候我们找到询问区间对应的二进制表示，查表得出答案。
这样子 FourRussian\tt{Four Russian} 预处理的时间复杂度就被优化到了 O(n)O(n)。

优化 33：基于状压的线性 RMQ\text{RMQ} 问题

对于同块的情况，考虑上述中用单调栈求解过程。令查询 [l,r][l,r] 最大值。l,rl,r 同块。
把 1∼r1\sim r 的元素放入单调栈，区间 [l,r][l,r] 的答案即为下标大于 ll 的第一个在栈中的元素（因为维护单调性）。
考虑这样想：将 1∼r1 \sim r 的元素加入单调栈时，可以用一个长度为块长 BB 的 0101 串表示 rr 所在块的每个元素是否在栈内。显然当 B≤64B \le 64 时容易状压成一个整数。
那么查询时用位运算截取 l∼rl \sim r 的部分转换成求状压后整数中末尾连续的 00 的数量。容易用 O(1)O(1) 做到。
那么要使 B≤64B \le 64，不妨就取 B=log⁡nB=\log n，预处理复杂度就是 O(n)O(n)，每次查询 O(1)O(1)，总时间复杂度为 O(n+q)O(n+q)。
（似乎用期望可以玄学优化，如果出题人要卡，暴力就会被放过。这里不写了。）

总结

算法名称时间复杂度空间复杂度综合分析
step1.ST 表O(nlog⁡n+q)O(n\log n+q)O(nlog⁡n)O(n\log n)朴素简单，适合新手入门。
step2.离线单调栈O(qlog⁡q+qlog⁡n)O(q \log q+q \log n)O(n+q)O(n+q)空间复杂度较低，时间复杂度朴素。
step3.线段树/树状数组O(n+qlog⁡n)O(n+q\log n)O(n)O(n)算法简单朴素，优点不突出。但好想且好写。熟记模板即可。
step4.分块O(nlog⁡log⁡n+q)O(n \log \log n+q)O(nlog⁡log⁡n+q)O(n \log \log n+q)常数较大，复杂度分析复杂，但实现简单
O(n+q)O(n+q)同上±1RMQ\pm1\text{RMQ} 优化。
O(n+q)O(n+q)同上基于状压的优化。

习题

P3865 【模板】ST 表 & RMQ 问题
P3793 由乃救爷爷
P6640 [BJOI2020] 封印
P2048 [NOI2010] 超级钢琴
P3295 [SCOI2016] 萌萌哒
P12736 [POI 2016 R2] 圣诞灯链 Christmas chain
点个赞吧！

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...