浅谈——RMQ问题
chenzefan
·
·
算法·理论
## step1.倍增法（ST 表）
最朴素的方法。时间复杂度为 $O(n \log n+q)$。
预处理时间复杂度 $O(n \log n)$，每次查询 $O(1)$。
以求**最大值**为例。
### 定义
定义 $f_{i,j}$ 表示区间 $[i,i+2^j-1]$ 的区间最大值。
### 初始化
$f_{i,0}$ 表示区间 $[i,i]$ 的结果，即 $a_i$。故有 $f_{i,0}=a_i$。
### 转移
由于区间最大值支持合并，则显然区间 $[l,r]$ 可以由 $[l,mid]$ 和 $[mid+1,r]$ 合并而来。$mid=\frac{l+r}{2}$。回归定义，可以得出转移方程：
$$
f_{i,j}=\max\{f_{i,j-1},f_{i+2^{j-1},j-1}\}
$$
预处理复杂度为 $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]);
```
### 询问
目前已经求出了 $f$ 数组。
询问区间 $[l,r]$ 的最大值。考虑用 $f$ 去覆盖应有区间。
显然我们可以令 $k=\log_2\{r-l+1\}$。
那么答案就是 $\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)$。
优点：易懂。
## step2.离线单调栈
复杂度 $O(q \log q+q \log n)$。
排序复杂度 $O(q \log q)$，每个询问二分 $O(\log n)$。
### 方法
离线下来所有询问，按右端点 $r$ 排序。然后每次在序列 $a$ 上找到当前询问的右端点 $r$ 处，并把找到的元素压入到单调栈中。这样，对于每个询问时，单调栈中存储的值满足在 $a$ 中的位置 $\le r$。只需找到序列中第一个 $\ge l$ 的值。显然可以二分来找。
优点：空间复杂度 $O(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(\log n)$，总共为 $O(n+q\log n)$。
优点：模板且没有思维含量。
那么树状数组也能做。
~~似乎没必要。~~
## step4.四毛子前置算法（分块）
四毛子算法原名 $\tt{Four Russian}$。这里分析前置算法——分块。
### 方法
考虑将原序列每 $B$ 个分进一个块，则共有 $\frac{n}{B}$ 个块。
每次询问情况可分为以下几种：
- 块内：直接遍历找最大值。
- 相邻块中：前面块的一段后缀的贡献和后面块的一段前缀的贡献取并。
- 间隔很多块：考虑第一个块后缀和最后一个块的前缀，中间的整块直接用 ST 表 $O(1)$ 查询。
梳理一下就是：
- 对于每一个块预处理前缀最大值和后缀最大值。复杂度 $O(\frac{n}{B}\times B)=O(n)$。
- 对于每个块总体贡献建立 ST 表，那么也就是 $\frac{n}{B}$ 个块之间的 ST 表，时间复杂度为 $O(\frac{n}{B}\log\frac{n}{B})$。
再发掘一下，发现每次询问最坏情况为同块时，需暴力扫一遍，则时间复杂度为 $O(qB)$。其余情况直接可以 $O(1)$ 解决。考虑如何优化？
### 优化 $1$：块内 ST 表
我们是否可以在每个块内建立 ST 表呢？
答案显然，故时间复杂度为 $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 n$，得到时空复杂度都近似为 $O(n \log \log n+q)$。
优点：实现简单。
### 优化 $2$：$\pm1\text{RMQ}$ 问题
继续优化同块的情况。
>[oi_wiki](https://oi-wiki.org/ds/cartesian-tree/) 对于**笛卡尔树**的解释。
不难发现，通过构建原序列的笛卡尔树，即可把原本的 $\text{RMQ}$ 问题转化成了树上 $\text{LCA}$ 问题，继续转换，就变成了 $\pm1\text{RMQ}$ 问题。可以预处理 $O(n)$，每次查询 $O(1)$，共 $O(n+q)$ 的时间内解决。
$\pm1\text{RMQ}$ 问题定义为相邻两个值的差为 $\pm1$。即 $\forall i \in \{x|1 \le x < n\},|a_i-a_{i+1}|=1$。
引用一段文字（摘自 OI_wiki，进行了格式优化）：
> 由于 $\tt{Four Russian}$ 算法的瓶颈在于块内 $\text{RMQ}$ 问题，我们重点去讨论块内 $\text{RMQ}$ 问题的优化。\
> 由于相邻两个数字的差值为 $\pm1$，所以在固定左端点数字时 长度不超过 $\log n$ 的右侧序列种类数为 $\displaystyle\sum_{i=1}^{\log n} 2^{i-1}$，而这个式子显然不超过 $n$。\
这启示我们可以预处理所有不超过 $n$ 种情况的最小值-第一个元素的值。\
在预处理的时候我们需要去预处理同一块内相邻两个数字之间的差，并且使用二进制将其表示出来。\
在询问的时候我们找到询问区间对应的二进制表示，查表得出答案。\
这样子 $\tt{Four Russian}$ 预处理的时间复杂度就被优化到了 $O(n)$。
### 优化 $3$：基于状压的线性 $\text{RMQ}$ 问题
对于同块的情况，考虑上述中用单调栈求解过程。令查询 $[l,r]$ 最大值。$l,r$ 同块。
把 $1\sim r$ 的元素放入单调栈，区间 $[l,r]$ 的答案即为下标大于 $l$ 的第一个在栈中的元素（因为维护单调性）。
考虑这样想：将 $1 \sim r$ 的元素加入单调栈时，可以用一个长度为块长 $B$ 的 $01$ 串表示 $r$ 所在块的每个元素是否在栈内。显然当 $B \le 64$ 时容易状压成一个整数。
那么查询时用位运算截取 $l \sim r$ 的部分转换成求状压后整数中末尾连续的 $0$ 的数量。容易用 $O(1)$ 做到。
那么要使 $B \le 64$，不妨就取 $B=\log n$，预处理复杂度就是 $O(n)$，每次查询 $O(1)$，总时间复杂度为 $O(n+q)$。
~~（似乎用**期望**可以玄学优化，如果出题人要卡，暴力就会被放过。这里不写了。）~~
# 总结
|算法名称 |时间复杂度 |空间复杂度 |综合分析 |
|:---------:|:---------:|:---------:|:---------:|
|step1.ST 表|$O(n\log n+q)$|$O(n\log n)$|朴素简单，适合新手入门。|
|step2.离线单调栈|$O(q \log q+q \log n)$|$O(n+q)$|空间复杂度较低，时间复杂度朴素。|
|step3.线段树/树状数组|$O(n+q\log n)$|$O(n)$|算法简单朴素，优点不突出。但好想且好写。熟记模板即可。|
|step4.分块|$O(n \log \log n+q)$|$O(n \log \log n+q)$|常数较大，复杂度分析复杂，但实现简单|
|^|$O(n+q)$|同上|$\pm1\text{RMQ}$ 优化。|
|^|$O(n+q)$|同上|基于状压的优化。|
## 习题
[P3865 【模板】ST 表 & RMQ 问题](https://www.luogu.com.cn/problem/P3865)
[P3793 由乃救爷爷](https://www.luogu.com.cn/problem/P3793)
[P6640 [BJOI2020] 封印](https://www.luogu.com.cn/problem/P6640)
[P2048 [NOI2010] 超级钢琴](https://www.luogu.com.cn/problem/P2048)
[P3295 [SCOI2016] 萌萌哒](https://www.luogu.com.cn/problem/P3295)
[P12736 [POI 2016 R2] 圣诞灯链 Christmas chain](https://www.luogu.com.cn/problem/P12736)
点个赞吧！