RMQ


RMQ (Range Minimum Query),指求区间最小值。普通的求区间最小值的方法是暴力。

对于一个数列:

\[A_1,~ A_2,~ A_3,~ \cdots,~ A_n
\]

对于一个给定的区间\([l, ~r], ~1≤ l ≤r ≤ n\),\(\min \{A_l, A_{l + 1}, \cdots,A_r\}\)的计算就是RMQ问题。

此解法为\(\text{Sparse-Table}\)解法,简称\(ST\)表。

  • 预处理:预处理为对数据进行\(n\log n\)的时间复杂度的处理

    令\(d(i, j )\)为\(A_i, A_{i + 1}, \cdots, A_{i + 2^j - 1}\)的最小值,即\(d(i, j)\)的区间长度为\(2^j\),这里用到的是倍增的思想。

    则\(d(i, j - 1)\)为\(A_i, A_{1 + 1}, \cdots, A_{i + 2^{j - 1}-1}\)的最小值,区间长度为\(2^{j-1}\)

    同样地\(d(i + 2^{j - 1}, j - 1)\)表示的是\(A_{i + 2^{j-1}}, A_{i + 2^{j - 1} + 1}, \cdots, A_{i + 2^{j-1} + 2 ^{j - 1} - 1 = i + 2^j - 1}\)。

    所以显而易见:\(d(i, j)\)可以表示为:

    \[d(i,j) = \min \{d(i, j - 1), ~d(i + 2^{j - 1}, j - 1)\}
    \]

  • 查询:

    令\(k\)为满足\(2 ^ k ≤ R - L+ 1\)的最大整数,即\(k = \max\{t~|~2^t ≤ R - L + 1, t \in \mathbb Z^+\}\)。

    同样地:\(k =[ \log_2 (R-L + 1)]\),所以:\(\operatorname{Query}(L,R) = \min \{d(L,k),~d(R - 2^k + 1, k\}\)

    查询的时间复杂度为\(O(1)\)。

注意:由于每次\(pow(2,x)\)非常浪费时间,在计算机内部二进制可以表示为:\(1 << x\)。

代码:

namespace RMQ {

  	void init(int n) {
for (int i = 1; i <= n; i ++) d[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j ++) {
for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
} int query(int l, int r) {
int k = log2(r - l + 1);
return min(d[l][k], d[r - (1 << k) + 1][k]);
} }

注意init中的循环顺序不能颠倒,显而易见,\(j\)的值,即区间的长度,必须由小到大。

05-18 19:01