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的状态)