「编程笔记」ST表的实现与使用

2023年5月26日 0 条评论 174 次阅读 2 人点赞

ST表,全称SparseTable,也叫做稀疏表。是用来解决区间和和区间最大最小值问题的一种工具。其实推广开来,其可以用来解决任何可重复贡献(associative)问题。

使用条件

可重复贡献问题

ST表要求其处理的问题必须具有“可重复贡献”这一特征。具体是什么意思呢?

假设有操作F,使得F(a, b, c) == F(F(a, b), c) == F(a, F(b, c)),则称F符合可重复贡献问题的特征。

如图,不难发现max()最大值函数就符合可重复贡献问题的特征;读者可以自行验证,sum()min()等函数都符合这个特征,这也证明了ST表可以解决最大最小值以及区间和等问题。

元数据可不能改变噢

在使用ST表解决问题时,我们必须确保所有的查询结束前,ST表所对应的元数据都不改变。

有些数据结构(比如线段树)在元数据更新之后(比如原来的数组中,某个数值由3变成了5),可以有对应的事件复杂度比较低的方法对结构进行更新,以达到一边更新一边查询的效果。ST表则无法提供类似的方法,所以确保你的问题中没有要求在查询期间动态调整元数据的要求。

SparseTable意义与使用

接下来,我们采用由表及里的过程,先了解ST表的意义以及使用方法,之后再来说明如何生成ST表。

一些准备——向下取整的Log2函数

由于SparseTable的特性,无论是根据数据生成ST表,还是得到ST表后对数据进行查询,都会比较频繁的用到向下取整的log2函数,所以特地说明。我们对于向下取整的log2运算稍加分析,可以得到log2(x)向下取整的具体意义是:

对于某一个数N,返回可能的最大的数字n,使得2的n次方小于等于N,且2的n+1次方必定大于N。

比如对于7,log2(7)向下取整为2,2的2次方不超过7,但可以保证2的3次方一定大于7(8>7)。

了解了这个之后,让我们来看看SparseTable如何快速解决规模庞大的可重复贡献问题吧~

ST表中数据的意义

我们接下来选择一个经典的可重复贡献问题——区间最大值问题,作为示例。

假设我们有一个数组 {3, 2, 1, 4, 5, 9, 7}, 其数据元素个数为7,要求必须在非常低的事件复杂度内,查询某个特定区间(比如从下标0到下标5)的最大值。此时,如果直接循环求解,会导致复杂度随着查询区间长度不断增高,这就是ST表登场的时候啦。

如上图,对数组进行处理之后,就可以得到下方的二维数组,也就是我们大名鼎鼎的SparseTable——ST表。那么问题来了,图中ST表中的数据,到底具有什么含义呢?

首先需要知道的是,ST表正常情况下使用一个二维数组st[idx][pow]来储存。下面对这个二维数组每一个位置元素的意义做出解释:

  • 数组中,每一个特定位置(idx, pow)的值,都代表对应问题在某个区间的解。
  • 这个区间的开始坐标为idx。
  • 这个区间的长度为2的pow次方。

例如,对于区间最大值问题,假设原数组为arr,处理后得到的ST表中,st[1][2] = 5,则说明:原数组,从下标为1开始,长度为2^2=4的区间内,最大值是5。

特定区间的查询

知道了ST表的数据的意义,我们就可以着手解决特定区间查询问题。

这里需要注意的是,虽然ST表可以解决不同的可重复贡献问题,但是其在面对不同的可重复贡献问题时,最优查询方式可能有一定的区别。接下来,我们先通过上方的“区间最大值”例子,介绍一下区间最值问题的ST表查询。

合适的长度

首先,为了降低时间复杂度,我们希望用尽可能少的区间查询来拼凑出完整答案。可以证明,在ST表处理区间最值问题时,无论区间长度位置,我们都可以用ST表支持的两个区间,拼接出答案。比如对于区间(1, 6),可以由区间(1, 4)和区间(3, 6)区间的结果再求最值得到。对于“最值”问题,我们只需要保证选择的区间完整覆盖住所求区间,且不超过所求区间即可,而这多个区间允许有重复部分。

同时,为了保证所用区间尽可能少,每个区间就要尽可能大。这个时候,上方说到的log2向下取整计算就派上用场了。由于ST表代表的区间长度只能是2的n次方倍,所以,不超过区间范围的区间,其最长长度就是log(区间长度)向下取整。

比如对于(1,6)区间进行最值计算,log2(6)向下取整=2。说明只需要在合适的位置,用两个长度为2^2=4的区间覆盖即可。这代表了,我们要取的数据肯定在ST[idx][2]内——我们确定了pow。

合适的位置

我们已经知道了,只要位置安排合理,我们肯定能用两个长度为4的区间覆盖住(1, 6),那么这两个区间的位置,应该如何选择呢?

思考之后发现,我们肯定希望:

  • 第一个区间尽可能往左,也就是第一个区间的起始下标就是总区间起始下标1。
  • 第二个区间尽可能往右,也就是第二个区间的结束下标就是总区间结束下标6。

如上图,最终,我们可以得到:

  • 第一个区间为(1, 4),最大值为5。
  • 第二个区间为(3, 6), 最大值为9。

我们对这两个区间的最大值再求一次最大值即可,最终答案为max(5, 9) = 9

如果用ST表来计算,运算过程如下:

max(st[1][2], st[3][2]) 
= max(5, 9) 
= 9

是时候该自己实现ST表啦

如果您已经掌握了上面所说的,ST表的工作方式,那么恭喜你,欢迎来到ST表的DIY小课堂(bushi),在这里,你将学习如何通过自己的双手书写代码,为一个个数组生成属于他们自己的SparseTable!

初始化

初始值

根据ST表的定义,我们不难得到一个结论,即:

ST表的第一列数据 st[idx][0],与元数据arr[idx]完全相同。

更加准确的说,应该是 st[idx][0] == F(arr[idx]),其中F是本ST表所对应解决的可重复贡献问题。而由于我们以区间最大值为例,所以F(arr[idx]) == arr[idx],最终得到st[idx][0] == arr[idx]

表的长和宽

解决完初始值,还有另外一个问题,ST表的大小。

我们已经可以确定,表的行数(第一维下标)就是数据个数,比如对于7个数据的数组,生成的ST表肯定有7行。那么一个ST表有多少列呢?

ST表有多少列,取决于查询时最多可能用到第几列的数据。根据ST表的区间查询原理,不难得到,对于数据个数为N的数组,其ST表的最大列数,就是log2(N)向下取整。为什么呢?——因为最坏情况下,需要查询整个区间范围的数据,这时,查询区间长度最大,为N,查询时会调用到的区间的纵坐标(上文的pow),正是log2(N)向下取整。

解决完上面的问题,总算是万事俱备了,我们开始对ST表进行初始化:

逐步推出整个ST表

接下来的问题便是,如何计算ST表剩余其他部分的值。我们仍然需要从ST表的定义入手,不难发现,由于ST表中的数据本质上就是某个区间的结果,所以更大区间的结果可以由多个小区间结果拼接而来。意思是,我们可以通过表中左边列数据,一步步推出右边的列。(因为左边的列代表范围更小的区间,右边的列代表范围更大的区间,且相邻列的长度差一定是2倍)

由上面的思想启发,我们发现,对于某个位置的ST表st[idx][pow],其左边的ST表列数据已经可用(毕竟我们决定从左边往右边推,那么推到pow列的时候,ST表的pow-1列肯定已经完成计算了),其刚好可以由左边列的两个区间st[idx][pow-1]st[idx+2^(pow-1)][pow-1]相结合获得。

不要看公式复杂就放弃理解噢~,不难发现,其实其思想与上方”ST表的使用“中所提到的”区间查询“,运用了一样的思想。两个区间都尽可能大,同时一个尽量往左,另一个尽量往右。

上图就是对某个ST表位置进行求值的示意。知道了某个点的求值方法,我们只需要从上到下,从左往右不停循环,直到求出整个ST表即可。

需要注意,ST表中部分位置没有值,这是因为其对应的区间已经超出范围,比如st[4][2],计算可得,该区间结尾下标为7,但是原始数据个数为7,说明最大下标为6,故该点不应该存在数据,即使存在,查询时也肯定用不到(读者可以自行思考一下,为什么查询的时候不可能调用到这类数据点)。

实战环节!

至此,有关于ST表的所有理论思路都已经介绍完成啦,下面我们借用洛谷上的ST表模板题,来介绍一下ST表的实战,以及一些注意事项。

先放上题目AC代码:

#include <iostream>
#include <vector>
#include <algorithm>

using LL = int;

using namespace std;

LL st[100000][18] = {0};

LL log2Table[20] = {1};

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

void initLog2Table()
{
    for (int i = 1; i < 20; ++i)
    {
        log2Table[i] = log2Table[i - 1] * 2;
    }
    return;
}

LL logLowerBoundTable[100010] = {0};

// 这里实际上是在对上文提到的那个,重要的log2向下取整函数,进行事先缓存,以提高一些查询效率
void initLogLowerBound(const LL &numCnt)
{
    logLowerBoundTable[0] = -1;
    logLowerBoundTable[1] = 0;
    for (LL i = 2; i <= numCnt; ++i)
    {
        logLowerBoundTable[i] = logLowerBoundTable[i >> 1] + 1;
    }
}

int main()
{

    // init log2 table
    initLog2Table();

    // input data
    LL numCnt = 0;
    LL queryCnt = 0;
    numCnt = read();
    queryCnt = read();
    initLogLowerBound(numCnt);

    for (LL i = 0; i < numCnt; ++i)
    {
        st[i][0] = read();
    }
    
    // 这里是在计算,对于数据量N,ST表最多需要的列数是多少
    // 上文已经提及
    LL maxLayer = logLowerBoundTable[numCnt];
    for (LL curLayer = 1; curLayer <= maxLayer; ++curLayer)
    {
        // LL rightBound = numCnt - log2Table[curLayer];
        for (LL curIndex = 0; curIndex <= numCnt - log2Table[curLayer]; ++curIndex)
        {
            // calculate current arr value
            st[curIndex][curLayer] = max(st[curIndex][curLayer - 1], st[curIndex + log2Table[curLayer - 1]][curLayer - 1]);
            // cout << st[curIndex][curLayer] << "   ";
        }
        // cout << endl;
    }

    // deal with query
    LL left, right, intervalSize, maxLogNum, maxNum;
    for (LL curQuery = 0; curQuery < queryCnt; ++curQuery)
    {
        left = read();
        right = read();
        // turn into 0-index
        maxLogNum = logLowerBoundTable[right - left + 1];
        cout << max(st[left - 1][maxLogNum], st[right - log2Table[maxLogNum]][maxLogNum]) << "\n";
    }
}

no endl bro, use '\n' please...

这点与ST表这东西其实关系不大,只是提醒下各位,在这种IO看起来就非常耗时的情况下,使用endl进行换行,会出乎你意料的大幅度增加算法的耗时,同样,对于这道洛谷模板题,如果使用endl,几乎必定超时。对应的解决方案是使用'\n'进行换行。

你可能会问,为啥endl比'\n'更加耗时呢?至于这个问题,我也不敢说我完全了解,但可以确定的是,当你在输出流输出endl时,程序做的远远不止是换行这一件事,其中还包含了包括flush等很多其他的工作,这些工作会导致其开销远大于换个行这件事情本身。详细信息欢迎读者上网查询了解。

NF

NF

NFのBlog 站长(超低技术力) ACG人,假期划水/追番ing...

文章评论(0)