bangbang-ande 发表于 2023-7-24 00:10:51

c++ ST表(包含技术活动)

本帖最后由 bangbang-ande 于 2023-7-24 00:36 编辑

(前言:本次为回馈活动,所以本次的代码将不开放,文章最后会说到理由)

本节我们说说ST表,这是一个经典的求最大值的数据结构,专门解决RMQ问题,但是它无法解决动态区间最大值(即区间加数后求最大值的问题)

ST表的理解难度不小,但是编写起来很容易。

我们先回顾求区间最大值的问题描述:
题目描述 (来自于洛谷的ST表的模板题P3865)
给定一个长度为N的数列,和M次询问,求出每一次询问的区间内数字的最大值。

输入格式
第一行包含两个整数N,M,分别表示数列的长度和询问的个数。
第二行包含N个整数(记为 a[\i]),依次表示数列的第i项。
接下来M行,每行包含两个整数 l[\i],r[\i],表示查询的区间为,r[\i]]。
输出格式
输出包含M行,每行一个整数,依次表示每一次询问的结果。

样例输入
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
提示
对于 100% 的数据,满足 1 ≤ N ≤ 10^5,1 ≤ M ≤ 2×10^6,a[\i]∈,1 ≤ l[\i] ≤ r[\i] ≤ N。
时间限制:800ms;空间限制:125MB

这个题就是ST表的经典问题:RMQ问题。看到这个题,相信大家有一些想法,我们由浅入深来说说ST表的做法:

大家可以很快想到的第一种解法就是区间内一个一个数进行遍历,然后找到区间最大值。
这种方法确实很容易,容易到分数可能不怎么够(24pts),代码如下:
#include <iostream>
using namespace std;
int main(void){
        int n, m;
        cin>>n>>m;
        int a;
        for (int i=1; i<=n; i++){
                cin>>a;
        }
        int x, y;
        for (int i=1; i<=m; i++){
                cin>>x>>y;
                int lmax=0;
                for (int j=x; j<=y; j++){
                        if (lmax<a){
                                lmax=a;
                        }
                }
                cout<<lmax<<endl;
        }
} 时间复杂度为O(nm),如果n和m的值再大一点就超时了……

那么我们来想想有没有其它的方法……似乎有的Clever Boy就想出来了,我们可以用打表的方法求得最大值!虽然叫打表,但其实运用了动态规划的思想(不懂没关系)。简单的说,方法就是将每一种可能全部列出来,比如说有十个数据,那么我们的表中存储的是第一个~第二个的最大值,第一个~第三个的最大值,第一个~第四个的最大值,第一个~第五个的最大值……列出来的方法并不是单纯的一个一个模拟,而是根据已经算出来的可能进行组合获得全部的可能,时间复杂度为O(n^2+m),空间复杂度就很大了O(nm),时间和空间依旧没有得到巨大的改进。

ST表生而就是为了这个目的,因为它使用了倍增的思想,也就是2^n一步递增的方法。同时也因为2的特殊性(即$2^n=2^(n-1)+2^(n-1)),所以才有了这种方法。我们接下来正式来说ST表:

ST表是用二维数组构建的,我们用dp[\i]表示,那么i和j分别表示什么呢?准确来说,i表示的是原数组的第几个位置。而j的表示很关键,表示的是区间的长度。那么揭晓一下dp表示的就是区间的最大值。也就是说,我们存储的最大值并不是第二种方法的所有的最大值(也就是从所有的起点开始存,存储所有可能的区间),而是存一个次方的区间最大值。表格的讲解对我们后面的讲解很关键。

我们先讲解如何查询最大值:如果要查询某一部分的最大值,我们可以运用拆解的方法,举个例子,比如以下10个数:

数组12345678910
a[]3423184543697902256

加入我们打表已经完成,那么我们查询最大值的方法很简单,(假设查询最大值)我们只需要根据打好的表查询1-8的最大值;9-10的最大值进行比较得出最终最大值即可。这就是查询最大值的方法。

(下方的len表示的是l+r-1的值,也就是查询区间最大值的区间的长度)
此时很多同学都是????的,我解释一下:查询方法是这样的:我们秉承不重复的原则,根据2^j≤len的目的寻找$j$的最大值,然后取出并且比较2^j的最大值,然后将没搜索到的部分作为新区间,再进行搜索(这也就是分段查询),我们用下图表示:


这一个图就很明显的告诉我们了搜索的方式,大家可以尝试下边的例子:查询最大值,查询的图片如下:


那我们总结一下就是:


查询的时间可以简化为O(log n),根据题目的m次查询,时间复杂度为O(m log n);

那有没有更加简便的方法呢?有的有的,刚刚的操作是运用了每一次的查询都是不重复的,那么可不可以重复呢?答案是可以,还很可以!因为重复的查询不影响最大值,最大值永远是它,重复查询仅仅是重复包含了某一段区间,对最大值没有影响。
既然可以重复,那么我们不如想想用最少的次数去查询。相信大家已经想到了,我们在前面的分段查询时,第一次分段的区间是最大的,而且会发现它永远大过于区间的一半,永远包含在最终查询的区间当中。那么实际上我们可以这么做:



也就是在分段的时候先铺一层第一段区间,再倒着铺一段相同的区间,那么此时我们就可以将整一个区间都覆盖,并且不超出该区间!
那这样子的方式也最简单,最快速,时间复杂度降低到了前所未有的O(1)!有m次查询,所以时间复杂度为O(m)!

然后我们来讲讲构建:

数组12345678910
a[]3423184543697902256
(上方为例子)
根据例子的数据,我们先建立一个二维列表出来:

dp[][]12345678910
0
1
2
3

那么根据我们对dp二维数组的定义,即:
dp准确来说,i表示的是原数组的第几个位置。而j的表示很关键,表示的是区间的长度。那么揭晓一下dp[\i]表示的就是区间的最大值。
(Tips:这里的表格与数组的形式是倒置了,表格的横轴为下方的i,纵轴为下方的j)我们可以首先可以得出dp[\i]的最大值就是a的值,因为这一行表示的是区间,也就是的最大值,那区间内只有一个数的最大值不就是这个数本身吗,所以填表如下:

dp[][]12345678910
0
3423184543697902256
1
2
3

那么接下来的应该怎么填写呢?依旧很简单,dp=max(dp, dp),这一条式子也是很绝妙的,举个例子大家就明白了,dp求的是区间,也就是$$的最大值。那么我们想想,一共就两个数,那比较最大值不就是从dp和dp去比较吗?那如果是dp呢,它求的是区间的最大值,那么根据上面给出来的式子,我们可以知道:它通过寻找dp的最大值和dp的最大值可以得出,那这两个数怎么来的呢?由于我们的填表的顺序是从上到下的,所以这两个数在之前早就填完了,所以同理可以求出。最后填表如下(X表示不需要填,因为超过了数组的范围):

dp[][]12345678910
0
3423184543697902256
1342345456969909056X
245456969909090XXX
3909090XXXXXXX

那么这个时候就构建完了ST表,确实理解起来很简单,按照填表的数量,可以得出时间复杂度约为O(n log n)
最后我们来写一下程序(按照P3865写的,这个程序还不能拿满分,在原题目有提示满分的方法):
自己写,因为这一次有活动……

ST表完美解决了最大值的问题,时间复杂度为O(1),当然按照洛谷的问题来说,时间复杂度是O(nlog n+m),但是依旧不够全能。

最后,来填前言埋下的坑:
本次是第一次技术活动,大家可以通过我的描述,或者搜集更多的资料,去弄懂ST表的原理,自行写出ST表的程序,在洛谷平台中尝试测试P3865)
洛谷的题目链接:https://www.luogu.com.cn/problem/P3865
测试出的最高分数可以拿到的奖励:
24pts及以下:0鱼币
24pts~56pts(不包含56pts,也不包含24pts):2鱼币+1荣誉
56pts~80pts(不包含80pts):5鱼币+5荣誉
80pts~100pts(不包含100pts):8鱼币+8荣誉
100pts:12鱼币+10荣誉

如何发送自己的分数呢?这么发就行了:(仅仅截下测试点信息即可)

(因为我目前的评分只能评价一个鱼币,那么大家多发几条信息,我就能多评价一些,反正会补上就对了)
Have a great time,Everyone!
截止日期:2023.8.4

如果你水平不行的话,那么你可以尝试用运气的手段去要到鱼币(10%,2鱼币)

sfqxx 发表于 2023-7-24 08:49:24

前排支持

额外减小 发表于 2023-7-24 12:43:27

你已经做到这么高深的数据结构了啊...

琅琊王朝 发表于 2023-7-24 12:54:46

{:5_106:}

woshizhangpengp 发表于 2023-7-24 13:45:55

{:5_106:}

sfqxx 发表于 2023-7-24 16:04:13

{:10_256:}

sfqxx 发表于 2023-7-25 10:34:53

@zhangjinxuan

零之忆 发表于 2023-7-25 11:32:10

{:9_241:}
页: [1]
查看完整版本: c++ ST表(包含技术活动)