首页 > 代码库 > 分块学习
分块学习
分块是一种非常常用的技巧，他功能非常强大；然而相对的，它的时间复杂度较高，这也是它的缺陷。
设定每块大小为根号n，这样就把序列分为了n/根号n块
对于每一块，整体处理，不能构成一块的，暴力处理
代码:
for(int i=1;i<=n;i++) { a[i]=read();belong[i]=(i-1)/t+1; sum[belong[i]]+=a[i]; }
这样就完成了分块 例如10个数，belong[i]分别为 1 1 1 2 2 2 3 3 3 4
修改或查询时分三段区间
1. L~min(belong[L],R),闭区间。
2. belong[L]+1~belong[R],半开半闭区间。
3.(belong[R]-1)*t+1~t,闭区间。
这样就OK啦 例如区间求和
代码:
int query(int x,int y){ ans=0; for(int i=x;i<=min(y,belong[x]*t);i++) ans+=a[i]; for(int i=belong[x]+1;i<belong[y];i++) ans+=sum[i]; if(belong[x]!=belong[y]) for(int i=(belong[y]-1)*t+1;i<=y;i++) ans+=a[i]; return ans;}
以下3题练练手
T1 http://codevs.cn/problem/1080/ 线段树练习
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define N 100001using namespace std;int n,m,x,y,z,t,ans,a[N],belong[N],sum[N];inline int read(){ int x=0,f=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int query(int x,int y){ ans=0; for(int i=x;i<=min(y,belong[x]*t);i++) ans+=a[i]; for(int i=belong[x]+1;i<belong[y];i++) ans+=sum[i]; if(belong[x]!=belong[y]) for(int i=(belong[y]-1)*t+1;i<=y;i++) ans+=a[i]; return ans;}int main(){ n=read();t=sqrt(n); for(int i=1;i<=n;i++) { a[i]=read(); belong[i]=(i-1)/t+1; sum[belong[i]]+=a[i]; } m=read(); for(int i=1;i<=m;i++) { x=read();y=read();z=read(); if(x==1){a[y]+=z;sum[belong[y]]+=z;} if(x==2){printf("%d\n",query(y,z));} } return 0;}
T2 http://codevs.cn/problem/1081/ 线段树练习2
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define N 100001using namespace std;int n,m,q,x,y,z,t,ans,a[N],belong[N],tot[N];inline int read(){ int x=0,f=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int main(){ n=read();t=sqrt(n); for(int i=1;i<=n;i++) { a[i]=read(); belong[i]=(i-1)/t+1; } m=read(); for(int i=1;i<=m;i++) { x=read(); if(x==1) { y=read();z=read();q=read(); for(int i=y;i<=min(z,belong[y]*t);i++) a[i]+=q; for(int i=belong[y]+1;i<belong[z];i++) tot[i]+=q; if(belong[y]!=belong[z])for(int i=(belong[z]-1)*t+1;i<=z;i++) a[i]+=q; } if(x==2) { y=read(); printf("%d\n",a[y]+tot[belong[y]]); } } return 0;}
T3 http://codevs.cn/problem/1082/ 线段树练习3
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define N 200001using namespace std;long long n,m,x,y,z,t,w,R;long long sum[N],flag[N],ans,a[N],belong[N];inline long long read(){ int x=0,f=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int main(){ n=read();t=sqrt(n); for(int i=1;i<=n;i++) { a[i]=read();belong[i]=(i-1)/t+1; sum[belong[i]]+=a[i]; } m=read(); for(int i=1;i<=m;i++) { w=read(); if(w==1) { x=read();y=read();z=read();R=min(y,belong[x]*t); for(int i=x;i<=R;i++) a[i]+=z,sum[belong[i]]+=z; for(int i=belong[x]+1;i<belong[y];i++) flag[i]+=z; if(belong[x]!=belong[y]) for(int i=(belong[y]-1)*t+1;i<=y;i++) a[i]+=z,sum[belong[i]]+=z; } else { ans=0; x=read();y=read();R=min(y,belong[x]*t); for(int i=x;i<=R;i++) ans+=a[i]+flag[belong[i]]; for(int i=belong[x]+1;i<belong[y];i++) ans+=sum[i]+flag[i]*t; if(belong[x]!=belong[y]) for(int i=(belong[y]-1)*t+1;i<=y;i++) ans+=a[i]+flag[belong[i]]; printf("%lld\n",ans); } } return 0;}
分块学习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。