稀疏表(倍增优化DP)：区间最值问题

摘要: 元素不变的区间最值问题，稀疏表

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

给定一个数组，其中的元素可以修改，要查询数组中某个区间的和。过程中需要维护元素修改的操作，并且要高效查询区间的和。用线段树或者树状数组可以解决这个问题，在文章 线段树和树状数组：单点修改、区间查询，区间求和问题 中我们以单点修改为例解决了带修改的区间求和问题。如果整个过程元素没有更新，那么有更好的办法，就是用前缀和进行预处理，然后在预处理出的前缀和数组上高效查询区间和，参考文章 【模板】前缀和与差分。

类似的需求还有查询区间的最值。如果数组元素可以修改的话，还是可以考虑线段树或树状数组解决。参考文章 线段树：区间修改、区间查询，区间最值问题 和 树状数组维护区间最值。类似地，如果数组的元素不变，也是有更好的办法，思路也是先预处理，然后在预处理出的中间结果上查询区间的最值。具体的做法是倍增优化 DP，也称为稀疏表。本文我们来看一下这个算法。

区间最值问题

问题：给定一个数组，其中有 $N$ 个数字，对于一次查询，给定区间 [l ，r]，返回在这个区间内的最值为多少，一共有 $Q$ 次查询。

主流解法

这种区间最值问题，主流的算法有以下三种，在之前的文章中学习过第一种算法，本文是第二种算法，第三种算法以后有时间再看。

1. 线段树/树状数组，$O(n)$ 预处理 $O(q\log n)$ 在线查询。
2. 稀疏表(ST)，$O(n\log{n})$ 预处理 $O(q)$ 在线查询。
3. RMQ标准算法：先规约成LCA，再规约成约束RMQ，$O(n)$ 预处理 $O(q)$ 在线查询。

稀疏表：倍增优化 DP

稀疏表隐含了倍增法的思想。这方面可以参考文章 倍增法。

对于区间最值问题，当数组中数据不变时，RMQ 算法一般用较长时间$O(N\log N)$做预处理，然后可以在 $O(1)$ 的时间内处理每次查询。该方法称为稀疏表。

这种先预处理，在查询的做法与用前缀和处理大量区间和查询的思想相同。下面我们分别看预处理和查询部分是怎么做的。

<1> 预处理部分

dp[i][j] := 从第 i 位开始，连续 2^j 个数的最小值

例如: arr = [1, 2, 6, 8, 4, 3, 7]

• dp[2][1] 表示从第2位数开始连续2个数的最小值，即2,6中的最小值，所以 dp[2][1] = 2;
• dp[3][2] 表示从第3位数开始连续4个数的最小值，即6,8,4,3中的最小值，所以 dp[3][2] = 3
• dp[i][0] 表示第i个数字本身

求 dp[i][j] 的时候可以把它分成两部分，第一部分是从 $i$ 到 $i+2^{j-1}-1$ ，第二部分从 $i+2^{j-1}$ 到 $i+2^{j}-1$。

因为二进制数前一个数是后一个的两倍，所以可以把 $i$ 到 $i+2^{j}-1$ (即 dp[i][j] 表示的区间范围) 这个区间通过 $2^{j-1}$ 分成相等的两部分，进而写出转移方程：

dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])

在外层枚举 j: 1..(1<<j)<=N，含义：先更新每两个($2^{1}$)元素中的最小值，然后通过每两个元素的最小值获得每4个元素中的最小值，依次类推更新所有长度的最小值。

<2> 查询部分

查询区间 [l, r]，令 $k = log_{2}(r - l + 1)$，则区间 [l, r] 的最小值计算如下：

query(l, r) = min(dp[l][k], dp[r - (1 << k) + 1][k])

因为 dp[l][k], dp[r - (1 << k) + 1][k] 分别维护区间 $[l, l + 2^{k} - 1]$ 和 $[r - 2^{k} + 1, r]$。而 $l + 2^{k} - 1 \geq r - 2^{k} + 1$。

代码(C++, 模板)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class RMQ
{
public:
    RMQ(){}

    void init(const vector<int>& arr)
    {
        int n = arr.size();
        // 2 ^ m <= n
        // log2(2^m) <= log2(n)
        // m <= log2(n)
        int m = log2(n);
        dp.assign(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; ++i)
            dp[i][0] = arr[i]; //初始化
        for(int j = 1; (1 << j) <= n; ++j)
            for(int i = 1; i + (1 << j) - 1 <= n; ++i)
                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }

    int query(int l, int r)
    {
        int k = log2(r - l + 1);
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }
private:
    vector<vector<int>> dp;
};

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i)
        cin >> arr[i];
    cout << "数据: " << endl;
    for(int i = 0; i < n; ++i)
        cout << i << "  " << arr[i] << endl;
    RMQ rmq;
    rmq.init(arr);
    while(true)
    {
        int start, end;
        cin >> start >> end;
        cout << "查询区间: [" << start << ", " << end << "], 最小值：";
        cout << rmq.query(start, end) << endl;
    }
};

---