2020.4.24

前言

我会告诉你这篇博客是来补之前的锅的吗

之前写过一次ST表入门,但是原理并没有讲清楚,其实是我自己也没学懂,现在来补锅了

提醒:1<<k等价于$2^k$。


正文

首先明确,ST表是用来处理区间最值问题($RMQ$)的利器。它可以在$O(nlogn)$完成预处理之后凭借$O(1)$的查询时间复杂度极快地查询区间内的最大/最小值。

接下来是算法的介绍。

凭借我们朴素的情感,要在$O(1)$的时间内求出区间最值,我们想到的最暴力的做法是什么?记录f[i][j][i,j]间的最值。但是这样预处理起来要两重循环1-n,计算f[i][j]=min/max(f[i][j-1],a[j])就会耗费$O(n^2)$级别的时间。

那我们有没有什么办法来优化这一步骤呢?


这个时候就要发现一个非常有用的特性:最值允许区间重叠

也就是说,max(a,b,c)=max(max(a,b),max(b,c)),但a+b+c≠a+b+b+c,所以ST表并不能解决区间和值查询。

这样可以有什么用呢?我们可以尝试把一个大区间拆成小区间来求最值。小区间可以相互重叠,但是不能遗漏。

于是我们采用倍增的思想,把整个区间拆成若干个长度为2的整次幂的区间。即用f[i][j]表示$i \sim i+2^j$区间的最大值。

假定我们已经完成了这个预处理操作,我们应该如何查询区间最值呢?

比如我要查询区间[i,j]的最大值:

我们就在这一段区间的长度len(j-i+1)上动动手脚。找到一个最大k使得$2^k≤len$。其实也就是求一个$log_2^{len}$。在这一步呢可以通过STL自带的$log$函数来完成,因为$log_2^a = \frac{log_p^a}{log_p^2}$($p$取任意实数),用代码表示出来就是k=(int)(log(len)/log(2))

得到这个k之后,根据定义可以发现,$2^{k+1}$已经超出了$[i,j]$的范围,所以我们分别以$i,j$为起点/终点,$2^k$为区间长度,构造如下两个区间(绿色段的长度都为$2^k$):

左边的区间用$f[i][k]$表示,右边的区间用$f[j-(1<<k)+1][k]$表示。

$2^k$一定大于区间长度的一半,否则根据定义$k$将更大。所以这两个区间一定可以覆盖整个大区间。所以我们可以得到f[i][j]=max(f[i][k],f[j-(1<<k)+1][k]);


接下来就是预处理部分了。

首先,我们可以观察到f[i][0]=a[i]。所以我们读入的时候直接读入$f[i][0]$即可,若非题目要求,可以不另存原序列。

然后我们依然从小到大来看,因为f[i][j]表示的本身就是一个长度为$2$的整数幂的区间,所以我们不妨把它恰好拆成两半,即$f[i][j-1]$与$f[i+(1<<(j-1))][j-1]$。

拆成两个不漏的区间之后,我们就可以愉快的取最值了:f[i][j]=max/min(f[i][j-1],f[i+(1<<(j-1))][j-1])


模板部分:($n$个数字,$m$次查询输出最大值)

#include<bits/stdc++.h>
using namespace std;
int n,m,f[200010][20];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>f[i][0];
    int b=(int)(log(n)/log(2));
    for(int j=1;j<=b;j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    cin>>m;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        int p=(int)(log(r-l+1)/log(2));
        cout<<max(f[l][p],f[r-(1<<p)+1][p])<<endl;
    }
}

以后再回首看到有锅再补叭...

最后修改:2020 年 04 月 24 日 11 : 15 PM