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
页:
[1]