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]), 代码实现如下(这里使用 lrj 蓝书代码):
- void RMQ_init(const vector<int> &A) {
- int n = A.size();
- 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 RMQ(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]);
- }
来源: https://www.cnblogs.com/fan-jiaming/p/9739281.html