RMQ问题的ST算法 >> NoAlGo博客

RMQ问题的ST算法 » NoAlGo博客

RMQ问题(Range Minimum/Maximum Query，区间最值问题)，是指给定一个长度为n的数列A，回答若干次询问RMQ(A,i,j)(i,j<=n)（通常次数非常巨大），每次返回数列A中下标在i,j里的最小(大）值。
RMQ问题解法很多，如朴素算法、线段树、ST算法、RMQ与LCA互相转化等，不同算法思想及复杂度均有所差异。本文主要讲解其中非常高效的稀疏表算法（Sparse Table，ST算法）。

一 算法思想

ST（Sparse Table，稀疏表）算法是求解RMQ问题的经典在线算法，以O(nlogn)时间预处理，然后在O(1)时间内回答每个查询。

ST算法本质上是动态规划算法，定义了一个二维辅助数组st[n][n]，st[i][j]表示原数组a中从下标i开始，长度为2^j的子数组中的最值（以最小值为例）。

要求解st[i][j]时，即求下标i开始，长度为2^j的子数组的最小值时，可以把这段子数组再划分成两半，每半的长度为2^(j-1)，于是前一半的最小值为st[i][j-1]，后一半的最小值为st[i+2^(j-1)][j-1]，于是动态规划的转移方程为：

st[i][j] = min(st[i][j-1], st[i+2^(j-1)][j-1])

长度为2^j的情况只和长度为2^(j-1)的情况有关，只需要初始化长度为2^0=1的情况即可。而长度为1时的最小值是显然的（为其本身）。

现在问题是，st数组可以怎样加速我们的查询呢？

这也是算法的巧妙之处，假设求下标在u到v之间的最小值。先求u和v之间的长度len=v-u+1，然后求k=log2(len)，则u到v之间的子数组可以分为两部分：

• 以u开始，长度为2^k的一段
• 以v结束，长度为2^k的一段（可以计算得到起始位置为v-2^k+1）

注意，一般情况下这两段是重叠的，但是这两段的最小值中较小的一个仍然是u到v的最小值。于是

RMQ(u,v) = min(st[u][k], st[v-2^k+1][k])

Read full article from RMQ问题的ST算法 » NoAlGo博客