当前位置: 首页 > news >正文

ST表学习笔记

前置知识:倍增

其实倍增就是二进制拆分,因为有的数可能很大,我们按照2的幂次去查询,就能用 \(log_2n\) 的时间复杂度求解

ST 表

创建

ST 表运用的是倍增思想,我们可以用 \(O(nlogn)\) 的时间创建一个二维表,根据倍增思想就可以实现 \(O(1)\) 的区间最值查询(RMQ 查询)

我们这样定义:

定义 \(dp[i,j]\) 表示 \([i,i+2^j-1]\) 区间的最值,易得这个区间的长度为 $ 2^j$ ,那么根据倍增,这个区间可以分成两个长度为 $ 2^{j-1} $ 的区间,使用递推求解,递推式如下(max 可换成 min):

\[dp[i,j]=\max(dp[i,j-1],dp[i+2^{j-1},j-1]) \]

那么我们可以得出模板代码:

void init_st(){int k=log2(n);for(int i=1;i<=n;i++){dp[i][0]=a[i];}for(int j=1;j<=k;j++){for(int i=1;i<=n-(1<<j)+1;i++){dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}}
}

这里先枚举 \(k\) 是因为我们需要通过 \(k\) 来确定枚举的右区间,不然范围就会超过 \(n\)

查询

我们要查询的是一个 \([l,r]\) 区间,我们可以这样理解一下:

C__Users_Administrator.DESKTOP-JVRO3LD_AppData_Roaming_com.codexu.NoteGen_article_笔记_assets_6962c137-a758-4eac-b44a-4184ed33480c

我们只要找到一个最大的不超过 \(l,r\) 长度的 2 的幂次 \(k\),就能用建好的 ST 表计算答案。

而根据对数的定义:

\[\log_2n=a \to 2^a=n \]

所以,我们有($ [l,r]$ 表示 \(l,r\) 这个区间的长度):

\[\log_2[l,r]=k\to 2^k=[l,r] \]

所以 \(k\) 的答案是\(\log_2 r-l+1\),其中 \(r-l+1\) 求的是区间 \([l,r]\) 的长度。

那么就能够得出查询的公式:

\[k=\log_2r-l+1\\ ans=\max(dp[l][k],dp[r-2^k+1][k]) \]

所以代码就很好写:

int k=__lg(y-x+1);
cout<<max(dp[x][k],dp[y-(1<<k)+1][k])<<endl;

总结

ST 表是基于倍增思想完成的一种支持 RMQ问题(静态区间最值问题查询)的数据结构

ST 表能够实现 \(O(n\log n)\) 建表

尝试独自完成洛谷 P3865 【模板】ST 表 & RMQ 问题

http://www.hskmm.com/?act=detail&tid=29422

相关文章:

  • 谈一类易实现的非四毛子线性 RMQ
  • 我们学会在具体情境中做出恰当判断
  • 编译安装nginx
  • AutoGCL——AutoGCL: automated graph contrastive learning via learnable view generators
  • 【教程】无需第三方应用,Windows自带邮箱如何绑定QQ邮箱等第三方邮箱
  • 2025婚纱摄影影楼权威推荐榜:专业团队与创意拍摄打造梦幻婚礼
  • 为什么40岁后的快乐消失了
  • 分布式结构化存储系统-HBase访问方式
  • 【Azure APIM】自建网关(self-host gateway)收集请求的Header和Body内容到日志中的办法
  • [JAVA]JDK多版本设置
  • Google Veo3生成跳舞视频
  • 【PolarCTF】stackof
  • 新生赛 F,H,J 题解
  • pycharm跑python项目易出错的困难
  • 双端队列的0-1BFS
  • Python psycopg2 类库使用学习总结
  • [GenAI] RAG架构演进
  • 24NOIP游记——彼时彼刻
  • 嵌入式-C++面经1
  • 合并区间 - MKT
  • 如何防止员工向第三方 AI 泄露数据?滤海 AI DLP 全方位技术防护方案解析
  • 20232322 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 实验1 现代c++编程初体验
  • 冬天快乐
  • P2441M 见过的 tricks
  • 企业大数据战略定位
  • OpenAI加码个性化消费AI技术布局
  • 线性回归 C++ 实现
  • 内存分区
  • Spring Data JPA学习笔记