RMQ 转 LCA 再转 +-1 RMQ 的经典算法虽然小时候就听说过（指 lrj 的黑书），但是大概命运也跟什么 斐波那契堆 呀、Strassen Algorithm 呀什么的一样，属于理论更优但是因为常数太大而从来没写过的东西，
但是最近看到的一个十分 practical 的基于分块大法、单调栈和位运算的版本，不需要考虑 LCA，代码超短，而且常数很低！
Table of Contents
先回顾一下 RMQ 问题的一般做法，
可以说是实践中最 practical 的做法，支持修改这个性质太好了，维护其它相关信息也很方便，而且现在还有各种无责任 zkw 树，跑的也飞起，就连 atcoder library 的模板里写的都是 zkw 树，还可以用树链剖分，动态树推广到各种树上 RMQ 的情况，如果你只学一个算法那肯定选这个。
得益于 O(1) 复杂度的询问，是实践中使用仅次于线段树的做法。受到这个算法的启发也有人会想用其它的序列分割方法来做 RMQ，比如强行用树状数组，但是有点缘木求鱼囧。
离线的时候我们也可以选择单调栈，代码量更短。不过不是什么不可替代的性质，所以在比赛中出场机会不多，但是这一次在新算法里大放异彩！
看起来虽然有点多此一举，但是 RMQ 最早 O(n)-O(1) 的做法，都是从转 LCA 开始的。
以前我以为 RMQ 应该比 LCA 更简单一些，毕竟前者是序列上的问题，但这是错的。
它们之间的关系也许更像是 FFT 里对多项式的点集表示和系数表示。
Sqrt Tree 是一种线段树的 Alternative，可以解决所有线段树能维护的信息（半群），而且也像线段树那样可以支持修改，并且具有和 Sparse Table 一样的 O(1) 询问复杂度，缺点是修改操作的复杂度为 O(sqrt(n))。
思想也非常简单就是递归的进行分块，然后巧妙的使用位运算，和我们下面要提到的这种分块算法有很多相似之处。
分块单调栈位运算 O(n) – O(1) RMQ 名字也太长了，不如就叫 hqz 算法好啦！
Sparse Table 是静态 RMQ 非常有竞争力的一个算法，因为询问时间只需要 O(1)，
这里我们考虑使用分块大法来降低预处理的复杂度，通常分块一般是 b = sqrt(n)，但这里我们可以更小，让 b = log(n)（因为 ST 算法的预处理复杂度是 O(nlogn))。
那么唯一有问题的就是对于每个块内，如何也做到 O(1)。
最简单的想法，可能是对每一个块都跑一个小号的 Sparse Table。。。
但是这样会破坏我们预处理复杂度的要求，但是 overall 的复杂度是更优的，O(n/b*blogb)。。（那我们是不是能递归搞？）
不过有一种更好的方法，就是基于单调栈预处理出每个位置分别再询问宽度多大的时候，结果会发生变化。
而这个东西再 query 的时候居然是可以直接位运算 O(1) 得到目标位置的。。。于是问题就解决了。
习题
– BZOJ #1699. [Usaco2007 Jan]Balanced Lineup排队
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。