您当前的位置: 首页 >  算法

MangataTS

暂无认证

  • 0浏览

    0关注

    423博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

算法小讲堂之ST表算法详解

MangataTS 发布时间:2022-06-14 01:28:15 ,浏览量:0

ST表 前言 一、简介

ST 表是一种基于 倍增 思想,用于解决 可重复贡献问题 的数据结构

关于上述提到的 可重复贡献问题 其中最出名的就是 RMQ 问题,即区间最大(小)值,虽然线段树也能解决这个问题,但是各有优缺点,首先两者的预处理复杂度都是 n l o g 2 n nlog_2n nlog2​n 但是 ST 表的查询效率是 O ( 1 ) O(1) O(1) 而线段树的效率是 l o g n log_n logn​ 显然在一些大量区间重复贡献 查询 问题上来说, ST 表还是有一定的优势,但是 ST 表不支持数据的修改,也就是只能查,而线段树的修改和查询的复杂度都是 l o g 2 n log_2n log2​n

如果按照 一般的倍增 思想的话,我们每次都是跳 2 i 2^i 2i 步,那么查询的复杂度还是 l o g 2 n log_2n log2​n 但是由于我们查询的数据是满足 可重复贡献 的,所以我们只需要提前处理一下重叠的区间(其实就是将当前的区间分成两部分查过的区间,然后合并查询一下)

二、原理

在上面的简介中其实也说了 ST 表的原理,其实就是将我们当前查询的区间分成两部分,假设我们用 f [ j ] [ i ] f[j][i] f[j][i] 表示 [ j , j + 2 i − 1 ] [j,j+2^i-1] [j,j+2i−1] 这个区间的一个最大值,我们可以用下图来表示

在这里插入图片描述

前半段就是已经求出来的 [ j , j + 2 i − 1 − 1 ] [j,j+2^{i-1}-1] [j,j+2i−1−1] 的区间最大值,而后半段就是 [ j + 2 i − 1 , j + 2 i − 1 ] [j+2^{i-1},j+2^i-1] [j+2i−1,j+2i−1] 的区间最大值,那么整个 [ i , i + 2 j − 1 ] [i,i+2^j-1] [i,i+2j−1] 区间的最大值就是两区间的最大值的最大值,也就是去一个 m a x ( m a x ( [ j , j + 2 i − 1 − 1 ] ) , m a x ( [ j + 2 i − 1 , j + 2 i − 1 ] ) ) max(max([j,j+2^{i-1}-1]),max([j+2^{i-1},j+2^i-1])) max(max([j,j+2i−1−1]),max([j+2i−1,j+2i−1])) 即可

那么我们继续思考如何得到 f [ j ] [ i ] f[j][i] f[j][i] 的值呢?不难发现其实就是我们上面推导的式子: f [ j ] [ i ] = m a x ( f [ j ] [ i − 1 ] , f [ j + 2 i − 1 , i − 1 ] ) f[j][i] = max(f[j][i-1],f[j+2^{i-1},i-1]) f[j][i]=max(f[j][i−1],f[j+2i−1,i−1])

其实这里也能看出 2 i = 2 i − 1 + 2 i − 1 2^i = 2^{i-1} + 2^{i-1} 2i=2i−1+2i−1

不难得出预处理的递推代码:

void init(int n){
	for(int i = 1;i             
关注
打赏
1665836431
查看更多评论
0.0395s