标准 RMQ 算法简记

DPair · 2021-08-14 08:00:27 · 个人记录

本文同步发布于个人博客qwq

upd:感觉之前写的有点问题，于是把所有准确数都加上了 O 符号

瞎写的，有什么问题赶紧来喷我

学习自https://ljt12138.blog.uoj.ac/blog/4874，写的比我不知道高到哪里去了

就是一个严格 O(n)-O(1) RMQ 的东西，不过 OI 中应该没什么用（（

期望 O(n)-O(1) 那个就够了，常数又小又好写又没人卡你

算法流程大概是这样的

首先我们给序列整一个笛卡尔树，这样就把 RMQ 转化成了 LCA 问题

然后我们知道我们可以 RMQ 求 LCA

看到这里你可能觉得建树是意☆义☆不☆明的操作

不过我们看看 LCA 跑 RMQ 的性质，发现我们 RMQ 求 LCA 时是拉出了树的欧拉序

然后发现这东西相邻两个数的差距最多为 1

这东西叫做 ±1 RMQ

看到这里你可能觉得这还是意☆义☆不☆明的操作

不过我们发现差分之后，序列本质不同的区间减少了

想想我们期望 O(n)-O(1) RMQ 的做法？那个救爷爷的套路？

不会也不要紧，反正你往下看也能看懂

我们序列分块，块长先整个 B

然后我们直接整块序列建 ST表，复杂度 O({n\over B}\log n)

然后我们刚才不是说了？本质不同区间减少了？

发现长度为 B 的本质不同区间就 O(2^B) 个

因此这部分枚举+存在表里面，就可以处理散块查询，配合整块查询可以做到 O(1) 查询

取 B=O(\log n) ，发现上面那一堆都是 O(n)

然后我们就得到了 O(n)-O(1) 的 ±1 RMQ，得到了 O(n)-O(1) 的 LCA，得到了 O(n)-O(1) 的标准 RMQ 算法