RMQ问题是算法竞赛中常见的题目类型。

题目模型一般是这样的，给定一个数列A，定义操作query(l, r)，求A[l…r]中的最大或者最小值。求最大和求最小其实本质上是一样的（将元素转化为其相反数，即可转化该问题），下文就主要以求最小为例来展开讨论。

这篇博文主要对RMQ问题的思路和算法进行整理，以及RMQ问题相关题目的解题思路。

思路和算法

Sparse-Table算法

该算法的时间复杂度为O(nlogn), 思路简单，编码难度低。

定义s(i, j)为，从数组下标i开始，长度为2^j的范围内的最小值。

很容易可以推出s(i, j) = min{ s(i, j-1), s(i+2^j-1, j-1) }

在处理问题时，可以先将s数组初始化，然后对于query(l, r)的查询可通过计算 min{ s(l, k), s(r-2^k, k) }, 其中k是满足2^k <= r-l+1的最大整数，而来。

相关题目整理

…待续