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