分块学习-白红宇

分块学习

阅读量：4973 次

发布时间：2019-06-12

本文共 2619 字，大约阅读时间需要 8 分钟。

分块是一种非常常用的技巧，他功能非常强大；然而相对的，它的时间复杂度较高，这也是它的缺陷。

设定每块大小为根号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

以下3题练练手

T1 线段树练习

#include
      
       #include
       
        #include
        
         #include
         
          #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

单点修改，区间查询

T2 线段树练习2

#include
      
       #include
       
        #include
        
         #include
         
          #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

单点查询，区间修改

T3 线段树练习3

#include
      
       #include
       
        #include
        
         #include
         
          #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