(C++) ST 表 详解
本帖最后由 柿子饼同学 于 2022-8-26 17:26 编辑ST 表 (C++版)
ST 表 的应用
ST 表 用于静态查找区间最值.
在一个数组中 , 给定一段区间 问你这段区间里的 最大值 / 最小值 是啥.
普通的方法我们当然可以从 L 到 R 遍历一遍 , 但是 , 当元素特别多 ,L, R太大 , 询问次数很多时 , 就会非常的慢{:10_245:}
这让我们想到了预处理, 这样不管问什么 , 我们都可以很快回答出来 !{:10_279:}
于是 , 就有了 ST表 这么一个东西
原理
首先我们有一个数组 arr[ ] 来装值
我们定义一个二维数组 dp[ ][ ] (是的 , ST 表其实是一种动态规划的思想)
dp 表示 arr 的第 i 个元素和它后面 2 ^ j 个元素中的最大值 , 区间是
为什么这样定义呢 ?
因为每个整数都可以表示成 2^x + 2^y + ... 这样的形式
我们可以通过拼接的方式把目标区间用它 "拼" 成一个完整区间
例如 , 区间 的最大值可以用 dp, dp 和 dp 的最大值来表示
( dp -> -> , 以此类推 )
但是这样有点麻烦 , 有没有更快的方法呢 ? {:10_266:}
当然有 ! {:10_256:}
我们可以直接把它的最大值表示为 dp 和 dp 的最大值
看图 :
由于是取最值 , 所以重叠也没关系 , 只要到整个区间就行了
那我们怎么确定两个小区间的长度呢 ?
就是看大区间最大能 "装下" 2 的几次方 , 假设大区间长度是 l , 则一个小区间长度就是 log2 ( l ) 向下取整
由于 log 函数比较浪费时间 , 所以我们选择预处理 , 反正精度不高 , 我们有如下的递推式 : ( 这个就是个小公式 , 记住就行了 )log_2 = log_2 + 1; " >> " 是左移符号 , 可以理解为除以 2 的多少次方 , i >> 1 就是 i / 2 的意思
1 << x 就是 2 ^ x 的意思
然后我们就可以读入数据了 , 我们其实不需要单独的数组来存值 , 还记得 dp 的定义吗?
我们把 dp 存入值就好了 , 因为 2 ^ 0 == 1, 区间长为1,最大值就是它本身{:10_257:}
然后 , 就到了 dp 数组的预处理部分 :
由于 dp 第二维是表示 2的次方 , 所以每次增加就会乘 2 , 这个要注意
代码如下 :for(int j = 1; j <= log_2; j++){ // 第一层枚举 j, 小区间长度
for(int i = 1; i + (1<<j) - 1 <= n; i++){ // 第二层枚举开始的下标, 注意不要越界
dp = max(dp, dp);
}
}
原理可以看上图 , 一个大的区间最值等于它分成的两个小区间的最值
以上我们可以写一个初始化函数 :void init(){
for(int i = 3; i <= n; i++) log_2 = log_2 + 1;
for(int j = 1; j <= log_2; j++){
for(int i = 1; i + (1 << j) - 1 <= n; i++){
dp = max(dp, dp);
}
}
}
然后就是我们处理询问的区间
我们先求出 L 到 R 有多少个元素 , 一共是 R-L+1 个{:10_261:}
还记得我们的重叠取法吗?{:10_245:}
根据以上内容我们可以写出代码了吧{:10_256:} :
int query(int l, int r){
int t = log_2;
return max(dp, dp);
}
好啦, 贴上完整代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dp;
int log_2;
int n, q;
void init(){
for(int i = 2; i <= n; i++){
log_2 = log_2 + 1;
}
for(int j = 1; j <= log_2; j++){
for(int i = 1; i + (1<<j) - 1 <= n; i++){
dp = max(dp, dp);
}
}
}
int query(int l, int r){
int t = log_2;
return max(dp, dp);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0); // 读入优化
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> dp;
init();
int l, r;
while(q--){
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}
{:10_297:}~感谢观看~{:10_298:}
@青出于蓝 @小伤口 @tommyyu 高级{:10_254:} 青出于蓝 发表于 2022-8-26 17:16
高级
{:10_254:} 有意思！{:10_279:} 一点点儿 发表于 2022-8-26 17:30
有意思！
{:10_254:} 感谢分享 hornwong 发表于 2022-8-26 17:48
感谢分享
{:10_254:} 牛 专业{:10_275:} aaron0919 发表于 2022-8-26 19:02
牛
{:10_254:} desc 发表于 2022-8-26 19:06
专业
{:10_254:} 受益匪浅{:9_236:} 小伤口 发表于 2022-8-26 20:01
受益匪浅
{:10_254:} {:10_275:} {:5_101:} tommyyu 发表于 2022-8-26 20:24
感谢~ {:10_275:} 1molHF 发表于 2022-8-27 08:07
{:10_254:} {:10_275:}
页:
[1]
2