这篇文章上次修改于 481 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(6): Sparse Table (ST 表)

简介

ST 表 是一个数据结构，用于计算RMQ问题，其思想基于动态规划

RMQ问题

RMQ即Range Minimum / Maximum Query，区间的最大值最小值查询，即求区间最值的问题。

内容：

给含有n个元素的数组a，有多次查询，每次查询有变量L，R，问区间[L, R] 中的最大/小值。

分析：

解法1

对于区间L，R，只要遍历它们就可以找到最大值，这也是最暴力的解法，其时间复杂度为O(N2).

对于暴力解法，需要消耗大量的时间，多次查询都是一次新的查询，不利于降低时间复杂度。

解法2

因为有多次查找，不如创建数组d[n][n]，其中d[i][j] 表示区间i j中的最大值。其中我们有：

d[i][i] = a[i]
d[i][j] = max(d[i][j - 1], a[j])

对此，我们可以得到所有的查询的值，但时间复杂度并没有很大的下降，同时，空间复杂度提升到了O(N2)

对于这个d，我们将其称为表，我们可以发现，该表存储的多个区间高度重合，因此，该表的密度很高。

虽然解法2使用了DP的思想，但是仍有很大的进步空间。

ST表(稀疏表)

对于我们解法二，提到了该表的多个区间重合度问题，对于这一点，我们可以考虑能否降低区间重合度。

定义

ST表提出储存d[i][j]代表区间[i, i + 2^j) 左闭右开中的最值。

也可以储存最值的下标

查询

我们先假设该表已经完成预处理，该表的值已经储存完毕。

对于查询区间[x, y]，我们可知想其长度为y - x + 1, 对此，它必定能由两个区间并集产生。

两个区间特点：长度为2的幂值，两个区间可能重合，例如对于区间 [0, 13]

可得两个区间为 [0, 7] 和 [6, 13]。易得这两个区间的最大值也就是d[0][3]和d[6][3]

两个区间的最大值也就是这两个区间并集区间的最大值。接下来考虑如何获得这两个区间。

len = r - l + 1
i = log2(len) // 向下取整
result = max(d[l][i], d[r - (1 << i) + 1][i])

预处理

d[i][0] = i;

d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);

void init(const vector<int> & arr) {
    for (int j = 0; j < arr.size(); j++) {
        for (int i = 1; i + (1 << (j - 1)) <= arr.size(); j++) {
			if(j == 0) d[i][j] = i;
            else{
				d[i][j] = max(f[i][j - 1], d[i + 1 << (j - 1)][j - 1]);
            }
        }
    }
}

同样使用了DP的思路，对于区间[0, 7] （d[0, 3]）已知区间[0, 3] [4, 7] 分别是 d[0, 2], d[4, 2]

转化之后即为

d[0, 3] = max(d[0, 2], d[4, 2]);

实现的稀疏表类

class SparseTable {
public:
    SparseTable(const vector<int>& array) {
        this->array = array;
        this->n = array.size();
        this->k = log2(n) + 1;
        this->table.resize(n, vector<int>(k));

        buildTable();
    }

    int query(int left, int right) {
        int j = log2(right - left + 1);
        if (array[table[left][j]] <= array[table[right - (1 << j) + 1][j]]) {
            return table[left][j];
        } else {
            return table[right - (1 << j) + 1][j];
        }
    }

private:
    void buildTable() {
        for (int i = 0; i < n; ++i) {
            table[i][0] = i;
        }
        for (int j = 1; (1 << j) <= n; ++j) {
            for (int i = 0; i + (1 << j) - 1 < n; ++i) {
                if (array[table[i][j - 1]] <= array[table[i + (1 << (j - 1))][j - 1]]) {
                    table[i][j] = table[i][j - 1];
                } else {
                    table[i][j] = table[i + (1 << (j - 1))][j - 1];
                }
            }
        }
    }

    vector<int> array;
    vector<vector<int>> table;
    int n, k;
};

RMQ二维扩展

简略说明一下

d[a][b][c][d] 为 [(a, b), (c + 2 ^ a - 1, d + 2 ^ b - 1)]

按照同样思路完成即可。

部分应用例题

例题1：区间GCD

给定一个数字序列，多次询问[l, r]区间内所有数的最大公因数。

我们易发现gcd的连续性，和取最大值类似，故直接替换函数即可。

参考

Mai Icy

算法学习笔记6——ST表