数据结构——ST表

news/2024/12/15 23:49:47/

ST表的定义

ST表,又名稀疏表,是一种基于倍增思想,用于解决可重复贡献问题数据结构

倍增思想

这里列举一个去寻找一个区间内的最大值的例子

 

 

因为每次会将将区间增大一倍,所以才被称之为倍增思想 ,这种思想十分好用,建议友友们平常多多练习

ST表的适用范围

如果A区间和B区间可能有重叠的部分
但是并不影响A+B区间的答案,能通过 A区间答案 和 B区间答案 就加工出来
那么对应的区间询问,就是一个可重复贡献问题
例如:区间最大值,区间最小值、区间公约数等,但是区间求和就不符合这个要求
再例如:区间按位与、区间按位或,ST表都能高效地解决


ST表的优势和劣势

 RMQ问题(Range Maximum/Minimum Query)可以用ST表维护,也可以用线段树等结构维护
ST表的优势:构建过程时间复杂度0(n*logn),单次查询时间复杂度0(1),代码量较小
ST表的劣势:需要空间较大,能维护的信息非常有限,不支持修改操作

只能维护静态区间内的可重复贡献类问题,不能维护动态的

模版

预处理模版:

//st[i][j]表示的是以i为起点,长度为2^j的区间的最值
//外层循环遍历的是长度的指数,内层循环遍历的是起点 
for(int j=1;j<20;j++)
{for(int i=1;i+(1<<j)-1<=n;i++){st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}
} 

查询模版:

//maxn是统计给定区间的最值
//k是用来判断区间的长度
//l,r是给定的区间范围 
for(int i=1;i<=m;i++)
{cin>>l>>r;int k=log2(r-l+1);maxn=max(dp[l][k],dp[r-(1<<k)+1][k]);
} 

例题:

P3865 【模板】ST 表 && RMQ 问题

 

思路:十分板正的一个ST表板题,就是去求区间内的一个最大值,纯板题

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  int n, m;  
int l, r;  
int st[100005][20];  signed main() {  ios::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);  cin >> n >> m;  for (int i = 1; i <= n; i++) {  cin >> st[i][0];  }  for (int j = 1; j < 20; j++) {  for (int i = 1; i + (1 << j) - 1 <= n; i++) {  st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);  }  }  for (int i = 1; i <= m; i++) {  cin >> l >> r;  int k = log2(r - l + 1);  cout << max(st[l][k], st[r - (1 << k) + 1][k]) << "\n";  }  return 0;  
}

 P2880 [USACO07JAN] Balanced Lineup G

 思路:也是ST表的板题,只不过是去求一遍最大值的ST表,然后再去求一遍最小值的ST表,然后减去就可以了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int f_max[50005][17];
int f_min[50005][17];
int l,r;
signed main()
{cin>>n>>q;for(int i=1;i<=n;i++){cin>>f_max[i][0];f_min[i][0]=f_max[i][0];}for(int j=1;j<=16;j++){for(int i=1;i+(1<<j)-1<=n;i++){f_max[i][j]=max(f_max[i][j-1],f_max[i+(1<<(j-1))][j-1]);f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<(j-1))][j-1]);}}for(int i=1;i<=q;i++){cin>>l>>r;int k=log2(r-l+1);cout<<max(f_max[l][k],f_max[r-(1<<k)+1][k])-min(f_min[l][k],f_min[r-(1<<k)+1][k])<<"\n";}
}

P2251 质量检测

思路1:滑动窗口问题,可以直接单调队列解决,去寻找m区间长度的窗口内的最小值,但是和今天的主题不相符,这种写法就靠看官自己去琢磨了

思路2:ST表,这题是求区间内的最小值,但是却是给你规定了区间大小,让你找出整个区间的这么大小的最小值,直接预处理一遍,然后遍历即可,但是如果m不是2^k,就找到最大的k, 然后用m-(2^k)+1的k区间长度,去找最小值即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int st[1000005][25]; 
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>st[i][0];}for(int j=1;j<=21;j++){for(int i=1;i+(1<<j)-1<=n;i++){st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}int k=log2(m);for(int i=1;i+m-1<=n;i++){cout<<min(st[i][k],st[i+m-(1<<k)][k])<<"\n";}return 0;
}

P1890 gcd区间

思路:区间gcd也是一种可重复贡献问题,因此也可以用ST表,我们直接预处理一遍,然后直接跑即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int st[1005][15];
int l,r;
int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>st[i][0];}for(int j=1;j<=14;j++){for(int i=1;i+(1<<j)-1<=n;i++){st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}for(int i=1;i<=m;i++){cin>>l>>r;int k=log2(r-l+1);cout<<gcd(st[l][k],st[r-(1<<k)+1][k])<<"\n";}return 0;
}

P4155 [SCOI2015] 国旗计划

思路:这题其实一开始我也没看出来是ST表的题目,后来想了好久我才恍然大悟,我们首先来看题,每个士兵都有自己负责的一个区域,为L和R,然后呢,我们有m个边防站,然后我们要遍历第i个士兵必须参与的情况下,最少需要多少个哨兵

我们首先需要拆环为链,我们之间将这个数组拷贝一遍,再延伸出来一个长度,然后我们去处理士兵负责的范围,加入右区间的端点,小于左区间端点,那么我们就直接将右区间的端点+m即可,然后我们再去复制每个哨兵一次,其区间的值都+m

然后我们就跑ST表,表示从i开始往后2^j次方能够达到什么位置,如果是当前这个人的左区间+m的位置,那么就说明覆盖了整个哨所,那就是可以了,我们需要去处理一下

然后直接写即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int l,r;
struct node{int l;int r;int pos;
}a[400005];
int st[400005][25];
int sum[400004];
bool cmp(node a,node b)
{return a.l<b.l;
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>l>>r;if(l>r){r+=m;}a[i].l=l;a[i].r=r;a[i].pos=i;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){a[i+n].l=a[i].l+m;a[i+n].r=a[i].r+m;}for(int i=1,j=1;i<=2*n;i++){while(j<=2*n&&a[j].l<=a[i].r){j++;}st[i][0]=j-1;}for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=2*n;i++){st[i][j]=st[st[i][j-1]][j-1];}}for(int i=1;i<=n;i++){int flag=a[i].l+m;int ans=0;int p=i;for(int j=20;j>=0;j--){if(st[p][j]&&a[st[p][j]].r<flag){ans+=1<<j;p=st[p][j];}}sum[a[i].pos]=ans+2;}for(int i=1;i<=n;i++){cout<<sum[i]<<" ";}return 0;
}

 Frequent values

 

思路:我们应当用到题目说的有序,我们可以将每一种数视为一个桶,然后将每个桶内的个数去求出来,然后去记录每个桶的左端点和右端点,然后我们在询问的时候,然后我们去预处理桶的数目的ST表,表示从第i个桶开始长度为2^j次方的桶内的最大值,然后我们再去找两边的最大值,然后去处理三部分最大值的最大值即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int a;
int l[500005];
int r[500005];
int st[500005][24];
int num[500005];
int x,y;
void ini()
{memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(st,0,sizeof(st));memset(num,0,sizeof(num));
}
signed main()
{while(cin>>n){if(n==0){break;}ini();cin>>q;int len=0;int flag=-0x3f3f3f3f;for(int i=1;i<=n;i++){cin>>a;if(a!=flag){r[len]=i-1;len++;l[len]=i;flag=a;}st[len][0]++;num[i]=len;}r[len]=n;for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}for(int i=1;i<=q;i++){cin>>x>>y;if(x>y)swap(x,y);if(num[x]==num[y]){cout<<y-x+1<<"\n";}else{int ans=0;int L=num[x]+1;int R=num[y]-1;if(L<=R){int k=0;  while((1<<(k+1))<=R-L+1) k++;ans=max(ans,max(st[L][k],st[R-(1<<k)+1][k]));}ans=max(ans,max(y-l[num[y]]+1,r[num[x]]-x+1));cout<<ans<<"\n";}}}return 0;
}

 


http://www.ppmy.cn/news/1555439.html

相关文章

3D 视觉定位技术:汽车零部件制造的智能变革引擎

在汽车零部件制造领域&#xff0c;传统工艺正面临着前所未有的挑战。市场对于零部件精度与生产效率近乎苛刻的要求&#xff0c;促使企业寻求突破之道。而 3D 视觉定位技术&#xff0c;为汽车零部件制造开启了精准定位与智能化生产的新纪元。 3D 视觉定位系统的核心技术原理 3…

MVVM和MVC区别

概念深入理解 MVC&#xff08;Model - View - Controller&#xff09; Model&#xff08;模型&#xff09; 它是整个架构的数据核心&#xff0c;负责数据的完整性和一致性。这包括数据的存储结构定义、数据访问逻辑&#xff08;如数据库连接、查询语句的编写&#xff09;以及数…

C语言单元总结

黑色加粗表示刷题刷到这样的题 红色加粗表示可能重要 目录 单元一 程序设计宏观认识 C语言程序框架 C语言程序构成 标识符 程序开发过程 单元二 程序设计基础知识 数据类型 常量 &#xff08;1&#xff09;直接常量 &#xff08;2&#xff09;符号常量 变量 强…

04面向对象篇(D5_Thinking(D1_Thinking - 思考))

目录 一、为什么要谈论OOA、OOD、OOP&#xff1f; 二、你知道OOA、OOD、OOD对软件工程师的重要性&#xff1f; 三、DDD、OOA、OOD、OOP和OOT到底有什么区别和联系&#xff1f; 一、为什么要谈论OOA、OOD、OOP&#xff1f; OOA&#xff08;面向对象分析&#xff09;、OOD&am…

如何在RTTHREAD 的master上获得干净的vscode-clangd体验

在用clangd开发RTT吗&#xff0c;快来试试如何简单获得清晰干净的工作区 文章目录 在用clangd开发RTT吗&#xff0c;快来试试如何简单获得清晰干净的工作区简介操作步骤第一步 安装clangd第二步 生成compile_compand.json 文件第三步 执行scons --targetvsc第四步 打开stm32f10…

【Linux-ubuntu通过USB传输程序点亮LED灯】

Linux-ubuntu通过USB传输程序点亮LED灯 一,初始化GPIO配置1.使能时钟2.其他寄存器配置 二&#xff0c;程序编译三&#xff0c;USB传输程序 一,初始化GPIO配置 1.使能时钟 使能就是一个控制信号&#xff0c;用于决定时钟信号是否能够有效的传递或者被使用&#xff0c;就像一个…

EXCEL 数据透视表基础操作

目录 1 选择数据&#xff0c;插入数据透视表 2 选择数据透视表生成位置 3 出现了数据透视表的面板 4 数据透视表的基本结构认识 4.1 交叉表/列联表 4.2 row, column, cell 一个新增的筛选器&#xff0c;就这么简单 4.3 可以只添加 rowcell/值 &#xff0c;也可以colu…

Github----提交人不是自己

账号用户名都设置对的,但是提交人不是自己 解决 发现是用户名和账号都夹了"号导致 git config --global user.name "Your Name" git config --global user.email "your.emailexample.com"不用引号 git config --global user.name Your Name git …