分块算法 解决区间问题
2021/9/30 22:10:53
本文主要是介绍分块算法 解决区间问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
块的操作主要有:
block是块的大小
t是块的数量
st是每个块的开始的下标
ed是每个块的结束的下标
pos是每个元素对应块的下标
sum是对应块的元素的和
add是增量标记 用于区间修改+区间查询
核心代码如下:
const int MAX=10010; int n; int a[MAX]; int st[MAX],ed[MAX]; int pos[MAX]; int sum[MAX]; int add[MAX]; //区间修改 void change(int l,int r,int d){ int p=pos[l]; int q=pos[r]; if(p==q){ //情况1 区间位于一个块里面 for(int i=l;i<=r;i++){ a[i]+=d; } sum[p]+=d*(r-l+1); } else { //区间跨多个块 for(int i=p+1;i<=q-1;i++){ add[i]+=d; //完整的块里面的数据直接加上d } for(int i=l;i<=ed[p];i++){ //整块前面的散块 a[i]+=d; } sum[p]+=d*(ed[p]-l+1); for(int i=st[q];i<=r;i++){ //整块后面的散块 a[i]+=d; } sum[q]+=d*(p-st[q]+1); } } ll query(int l,int r){ int p=pos[l]; int q=pos[r]; ll ans=0; if(p==q){ //整块 for(int i=l;i<=r;i++){ ans+=a[i]; } ans+=add[p]*(r-l+1); } else { //有散块 for(int i=p+1;i<=q-1;i++){ ans+=sum[i]+add[i]*(ed[i]-st[i]+1); //先处理整块 } for(int i=l;i<=ed[p];i++){ //整合散块 ans+=a[i]; } ans+=add[p]*(ed[p]-l+1); for(int i=st[q];i<=r;i++){ ans+=a[i]; } ans+=add[q]*(r-st[q]+1); } return ans; } int main(){ int block=sqrt(n); int t=n/block; if(n%block) t++; for(int i=1;i<=n;i++){ st[i]=(i-1)*block+1; ed[i]=i*block; } ed[t]=n; for(int i=1;i<=n;i++){ pos[i]=(i-1)/block+1; //pos是第i个元素所在的块 } for(int i=1;i<=t;i++){ for(int j=st[i];j<=ed[i];j++){ sum[i]+=a[j]; //sum是第i块的区间和 } } }
这篇关于分块算法 解决区间问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现