标准 RMQ 算法简记

本文同步发布于[个人博客](https://dpair2005.github.io/articles/stdRMQ/)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 算法