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])\]
那么我们可以得出模板代码：
[code]void init_st(){        int k=log2(n);        for(int i=1;i

这个好，看起来很实用

过来提前占个楼

过来提前占个楼

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

谢谢分享，试用一下

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

谢谢楼主提供！

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

谢谢分享，试用一下

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

这个好，看起来很实用

热心回复！

东西不错很实用谢谢分享

谢谢分享，辛苦了

这个好，看起来很实用

yyds。多谢分享

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

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

过来提前占个楼