算法简介
Method of Four Russians 算法，也被称为四毛子算法，是一种受万人敬仰 的算法。
好吧，这其实是一种可以做到 O ( n ) \mathcal{O}(n) O(n) 预处理， O ( 1 ) \mathcal{O}(1) O(1) 查询的 RMQ 算法。
但普通的 RMQ 算法只能做到 O ( n log n ) \mathcal{O}(n \log n) O(nlogn) 预处理， O ( 1 ) \mathcal{O}(1) O(1) 查询。
算法实现
步骤如下：
- 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。
- 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。
- 注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1 1 1。
下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列：
• 设 t t t 为 Euler 序列长度。取 b = ⌈ log 2 t t ⌉ b = \left\lceil\frac{\log_2t}{t}\right\rceil b=⌈tlog2t⌉。将序列每 b 个分为一大块， 使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 O ( t b log t ) = O ( n ) \mathcal{O}(\frac{t}{b} \log t)=\mathcal{O}(n) O(btlogt)=O(n)。
• （重点）对于一个块内的 RMQ 问题，也需要 O ( 1 ) \mathcal{O}(1) O(1) 的算法。由于差分数组 2 b − 1 2^{b-1} 2b−1 种，可以预处理出所有情况下的最值位置，预处理复杂度 O ( b 2 b ) \mathcal{O}(b2^b) O(b2b)，不超过 O ( n ) \mathcal{O}(n) O(n)。
• 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。
1. 笛卡尔树
笛卡尔树是一种特定的二叉树，可由数列构造，在最值查询、范围top k 查询等问题上有广泛应用。
它具有堆的有序性，中序遍历可以输出原数列。
笛卡尔树的每个节点有两个属性：id 和 val。对于第一个属性，笛卡尔树满足二叉搜索树的性质，对于第二个属性，笛卡尔树满足堆的性质。
下面以满足小根堆性质的笛卡尔树为例。
比如说，对于这个序列：6 , 3 , 2 , 4 , 7 , 8 , 1 , 5，造出来的笛卡尔树就是：
在本题中，我们要采用一种特殊的笛卡尔树，即一个节点的子树是一段连续的序列。
可以看看上图是否满足这种性质。
容易看出，数组 a 在闭区间 [l,r] 上的最小值等同于笛卡尔树中下标为 l 和 r 的两个顶点的最近公共祖先（LCA）的值。
由此，RMQ 问题可以转化为 LCA 问题。
下面说明如何在 O ( n ) \mathcal{O}(n) O(n) 时间内实现这一转化。
咕咕咕。。。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220964.html原文链接：https://javaforall.net
