RMQ算法原理及实现

RMQ（Range Minimum/Maximum Query），区间最值查询问题，是指：对于长度为 $n$ 的数列A，回答若干次询问 $RMQ(i,j)$，返回数列A中下标在区间 $[i,j]$ 中的最小/大值。

这里介绍Tarjan的Sparse-Table算法，预处理时间为 $O(nlogn)$，但查询只需要 $O(1)$，并且常数很小，算法也很容易写出。

1）预处理：

　设 $A[i]$ 是要求区间最值的数列，$d[i, j]$ 表示从第i个数起连续 $2^j$ 个数中的最小值。(DP的状态)

　显然 $d[i][0]$ 的值就是 $A[i]$ (DP初值)，我们把 $d[i，j]$ 平均分成两段(因为 $d[i，j]$ 一定是偶数个数字)，从 $i$ 到 $i + 2 ^ (j - 1) - 1$ 为一段，$i + 2 ^ (j - 1)$ 到 $i + 2 ^ j - 1$ 为一段(长度都为 $2 ^ (j - 1)$)。于是我们得到了状态转移方程 $d[i, j] = min(d[i，j-1], d[i + 2^(j-1)，j-1])$

Code

void RMQ() {
  for (int i = 0; i < n; ++i) d[i][0] = a[i];
  for (int j = 1; (1 << j) <= n; ++j)
    for (int i = 0; i + (1 << j) - 1 < n; ++i)
      d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}

2）查询：

　假如我们需要查询的区间为 $(i,j)$ ，那么我们需要找到覆盖这个闭区间(左边界取 $i$，右边界取 $j$)的最小幂（可以重复，比如查询1，2，3，4，5，5不是2的任意次方，但我们可以查询1234和2345）。

　这个查询长度我们取范围小于等于区间长度的最大 $(2^k)$，这样我们查询 $i$ 到 $i + (2^k)$ 与 $j - (2^k) + 1$ 到 $j$ 的值，取二者最小值即可，代码实现如下：

int query(int L, int R) {
  int k = 0;
  while ((1 << (k + 1)) <= R - L + 1) ++k;
  return min(d[L][k], d[R - (1 << k) + 1][k]);
}