ST表封装
2026-08-12 13:27:50
发布于：浙江
47阅读
0回复
0点赞
主要写ST封装的定义和调用以及应用范围
定义：
//这里值写区间最大值和最小值，其他的逻辑基本相同
struct STMAX{
int f[N][21+1];
void intit(int n){
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int query(int l,int r){
int s=__lg(r-l+1);
return max(f[l][s],f[r-(1<<s)+1][s]);
}
};//区间最大值示例
struct STMIN{
int f[N][21+1];
void intit(int n){
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int query(int l,int r){
int s=__lg(r-l+1);
return min(f[l][s],f[r-(1<<s)+1][s]);
}
};//区间最小值示例
STMAX amax;//定义结构体数组
STMIN amin;
调用结构体：
amax.init(n);
cout<<amax.query(l,r);
amin.init(n);
cout<<amin.query(l,r);
范围：
| 运算 |
|---|
| 区间最小值 |
| 区间最大值 |
| 区间最大公约数 |
| 区间按位与 |
| 区间按位或 |
嘘~....
有帮助，赞一个