求RMQ O(n)-O(1)超详细讲解！

Question

一定要是超详细，贴代码就算了。
说废话有意思么？

Answer 1

说白了是一种动态规划。
我们用f[i][j]来表示区间[i,i+2^j-1]的最值，采用分块思想，我们可以把区间[i,i+2^j-1]平均分为两个区间，因为j>=1的时候该区间的长度始终为偶数，可以分为区间[i,i+2^(j-1)-1]和区间[i+2^(j-1)-1,i+2^j-1]，即取两个长度为2^(j-1)的块取代和更新长度为2^j的块，那么最小值就是这两个区间的最小值的最小值，转移方程为F[i,j]=min(F[i,j-1],F[i+2^(j-1),j-1])或F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1]).
这样我们就有了一个储存最值的数组，那么如何将它优化为O(1)呢？
这里就说得到ST算法：询问时取k=ln(j-i+1)/ln2即可，那么可以令A为i到2^k的块，和B为到2^k结束的长度为2^k的块;那么A，B都是区间[i,j]的子区间，所以即求A区间的最小值和B区间的最小值的最小值。这个时候动态规划为：RMQ(i,j)=min(F[i,k],F[j-2^k+1,k])。

Answer 2

emm虽然时间有点长但还是回答一下吧qaqaq
这个问题可以通过分块 + st表解决
我们可以将序列分成 log 块， 然后处理一下每个块的前缀和后缀最值， 然后我们预处理的时候就可以吧每一个块当成一个数来处理， 显然一共有(n/log(n))个数， 预处理的复杂度就是On的qwq 。
然后对于查询区间[l, r] 我们可以通过l所在块的后缀最值， r所在块的前缀最值， 和中间块的最值来得到我们最终的答案， 复杂度为O1.
当然当l r 在同一个块里的时候我们无法处理， 这时候只要暴力就好了吧qwqwq 虽然复杂度为log n 但是完全可以调参， 基本上是不可能被卡掉的， 而且可以算一下l， r 在同一块里的概率是非常小的对吧qwq 要卡的话估计就会被暴力跑过去了。

Answer 3

既然都来问 O(n)-O(1) 的 RMQ 了，那么 ST 表应当是已经知道了的。

众所周知，ST 表是 O(nlog n) 预处理 O(1) 查询的数据结构，那么如果我们将整个序列分成 O(n/log n) 个块，每一个块大小是 (log n)/2，那么我们就可以在 O(n) 的时间内预处理，并且通过预处理块内的前缀最值和后缀最值来做到 O(1) 查询跨块的询问。

接下来考虑块内的询问，我们考虑将序列建笛卡尔树，然后以深度为权值求最值，容易发现与原问题等价。

所以我们可以预处理所有的 2^((log n)/2)=\sqrt{n} 种 ±1 的状态中最小值所在位置，然后就可以 O(1) 查询块内的最值了。

顺带推销自己的博客？

Answer 4

这个方法巨复杂……貌似是先把RMQ通过笛卡尔树变成LCA，然后通过欧拉序列把LCA变成±RMQ，然后再通过一个什么分块的table在O(n)-O(1)时间内解决。

Answer 5

首先，你这问题问得不够专业。
其次，叙述得不够详细……
所以，答案需要你进一步解释后才能给出。。。