每捎京 发表于 2025-10-13 11:38:53

ST表学习笔记

前置知识：倍增

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

创建

ST 表运用的是倍增思想，我们可以用 \(O(nlogn)\) 的时间创建一个二维表，根据倍增思想就可以实现 \(O(1)\) 的区间最值查询（RMQ 查询）
我们这样定义：
定义 \(dp\) 表示 \(\) 区间的最值，易得这个区间的长度为$ 2^j$ ，那么根据倍增，这个区间可以分成两个长度为 $ 2^{j-1} $ 的区间，使用递推求解，递推式如下（max 可换成 min）：

\=\max(dp,dp)\]
那么我们可以得出模板代码：
void init_st(){        int k=log2(n);        for(int i=1;i

士沌 发表于 2025-10-29 00:48:17

这个好，看起来很实用

役魅肋 发表于 2025-11-13 10:05:37

过来提前占个楼

嫁蝇 发表于 2025-12-25 06:34:00

过来提前占个楼

厨浴 发表于 2026-1-5 17:17:43

懂技术并乐意极积无私分享的人越来越少。珍惜

湛恶 发表于 2026-1-7 04:53:12

谢谢分享，试用一下

贼瘁 发表于 2026-1-19 11:17:05

感谢分享，下载保存了，貌似很强大

闻人莹华 发表于 2026-1-20 14:58:08

谢谢楼主提供！

焦和玉 发表于 2026-1-22 11:40:08

很好很强大我过来先占个楼 待编辑

溥价 发表于 2026-1-25 12:38:02

谢谢分享，试用一下

劳暄美 发表于 2026-1-27 05:21:35

很好很强大我过来先占个楼 待编辑

溶绚 发表于 2026-1-27 06:28:39

这个好，看起来很实用

高清宁 发表于 2026-1-28 05:14:21

热心回复！

啸妹回 发表于 2026-1-28 08:28:27

东西不错很实用谢谢分享

膏包 发表于 2026-1-28 20:56:39

谢谢分享，辛苦了

咳镘袁 发表于 2026-1-30 03:03:47

这个好，看起来很实用

能氐吨 发表于 2026-2-1 05:23:38

yyds。多谢分享

孜稞 发表于 2026-2-3 00:52:51

鼓励转贴优秀软件安全工具和文档！

万俟谷雪 发表于 2026-2-3 05:03:05

喜欢鼓捣这些软件，现在用得少，谢谢分享！

拼潦 发表于 2026-2-5 03:12:14

过来提前占个楼
页: [1] 2
查看完整版本: ST表学习笔记