广为人知的做法：对数分块，$O(n)-O(\log n)$，期望查询复杂度 $O(1)$。
具体的：按 $B=O(\log n)$ 对原序列分块。每个块内部预处理前后缀最值，块间按照整个块内部的最值建立 ST 表。
查询时，如果查询的区间跨块，直接用第一个块的后缀最值、最后一个块的前缀最值以及中间其他所有块的整块最值做比较，复杂度是常数。
如果查询的区间太小，没有跨块，直接暴力。
神秘的做法：$\text{RMQ} \Rightarrow \text{LCA} \Rightarrow \pm 1 \text{ RMQ}$，太复杂，不实用。
广为人知的做法 2：单调栈 + 二分。将所有询问离线，按查询区间右端点升序排序。用单调栈从左往右扫过去，对于一个查询 $[l, r]$，我们在单调栈中二分查找出最小的不小于 $l$ 的下标，就是区间最值。
practical 的线性常数 RMQ：
先用对数分块。考虑如何搞定不跨块的查询。
对每个块，我们在块内用一个单调栈从左往右扫描。对于每个点，我们用一个二进制数（掩码）记录它左边哪些位置在单调栈内。
查询时，我们相当于要找到 $r$ 对应的单调栈中不超过 $l$ 的最小位置。对于 $B = O(\log n)$，这可以使用位运算在常数时间内完成。具体的：l + countr_zero(mask[r] >> l)（注意这是在块内的 0-indexed 索引，l 是查询左端点相对块左边界的偏移量而不是在整个数组中的下标，r 同理）即可。