一种比线段树还高效的区间算法

脚本之家 2022-09-23

The following article is from 小K算法 Author 小K算法

关注“脚本之家”，与百万开发者在一起

作者 | 小K

出品 | 公众号：小K算法（ID：xiaok365）

01故事起源

有N个数排列成一排，给定一个区间，如何快速找出区间内最大的数是多少呢？

02分析

首先想到的自然是从区间头开始，依次遍历完区间内的元素，这样就可以找出结果了。但这个复杂度是O(n)，肯定不是我们想要的。

再来分析一下有什么特点呢？
这些数不会更改，所以每个区间的结果是不会变的，是否可以把所有的区间结果先计算出来？

如果数据规模很小确实可以，一旦数据过大肯定就不行了，因为时间和空间都是O(n^2)。

再考虑一下，区间的最值是有很强的传递关系，这就引导我们可以把大问题化为小问题。

很显然，这就是一个标准的线段树模型，不过今天我们再换一个更加高效的算法，稀疏表。

03稀疏表

稀疏表的思想就是提前预处理数据，所以主要针对数据不变的情况，而线段树更加灵活，可以动态维护数据的变化。

首先还是将区间划分成很多的小区间。那如何划分更合理？
第2章节中，我们枚举了所有的区间情况，可以看出其实有很多重复的情况，比如下面[0,3]其实可以通过[0,1]和[2,3]组合出来。

可以根据长度划分区间。
设数组为a[i]，f[i][j]表示区间[i,j]的最大值。
则长度为1的区间总共有n个，f[i][i]=a[i]。

长度为2的区间总共有n-1个。

因为之前已经求出了长度为1的区间的最大值，所以区间长度为2的最大值可以通过区间长度为1的结果直接推出来。

接下来就考虑长度为3的区间了吗？
其实并不是，因为前面已经有了长度为1和2的，所以可以组合出长度为3和4的。

那就直接考虑长度为5的吗？
如果考虑为5的，那你怎么计算呢，前面的也推不出长度为5的结果啊，至少得有3个区间才能推出来。

所以接下来考虑长度为4的区间才是正解，总共有n-3个。

再接下来自然就是考虑长度为8的区间了，总共有n-7个。
但这里有个很明显的问题，就是我们的数组f[i,j]定义的不合理，因为里面很多的小区间没有用上，比如长度为3，5，6，7等，所以需要重新定义。

04状态压缩

可以将第二维用于表示区间长度，第一维表示区间起点，对第二维就可以进行状态压缩。
设f[i,j]表示从i开始，长度为2^j的区间的最大值，即区间[i,i+2^j-1]。

则长度为2^j的区间就可以通过左右2个长度为2^(j-1)的区间推出结果。时间和空间的复杂度都为O(nlogn)。

05区间分解

那查询结果的时候要怎么处理呢，我们只计算了长度为2^j的区间，并没有计算长度为3、5、7等区间的结果。

所以这个处理和线段树的思想也类似，需要进行区间分解。不过线段树可能分解成很多个区间，而稀疏表只需要分解成2个区间就可以了。

对于任意区间[a,b]，长度为b-a+1，总可以找到2个长度为2^j的区间，这2个区间组合起来可以完全覆盖[a,b]，其中j的值为log(b-a+1)。

左边的区间左端点从a开始，长度为2^j，即区间[a,a+2^j-1]。右边的区间右端点从b开始，长度为2^j，即区间[b-2^j+1,b]。

则区间[a,b]的最大值就是这两个区间中更大的那个，即max(f[a,j],f[b-2^j+1,j])。

06代码实现

代码实现了最大值和最小值的获取。

6.1

变量定义

int high[50000][17], low[50000][17], n, q;

6.1

预处理

void solve() {
    // 枚举区间长度，2^j<=n
    for (int j = 1; (1 << j) <= n; ++j) {
        // 枚举左端点i，右端点i+2^j-1<=n-1
        for (int i = 0; i + (1 << j) <= n; ++i) {
            high[i][j] = max(high[i][j - 1], high[i + (1 << (j - 1))][j - 1]);
            low[i][j] = min(low[i][j - 1], low[i + (1 << (j - 1))][j - 1]);
        }
    }
}

6.1

main函数

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> high[i][0];
        low[i][0] = high[i][0];
    }
    solve();
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        int j = (int) (log(b - a + 1.0) / log(2.0));
        int minHeight = min(low[a][j], low[b - (1 << j) + 1][j]);
        int maxHeight = max(high[a][j], high[b - (1 << j) + 1][j]);
        cout << maxHeight - minHeight << endl;
    }
    return 0;
}