分块的思想在于将一个区间分成多块，利用整块处理的方式来提高程序运行的速度。分块十分灵活能够解决多种问题，这些问题有些线段树可以解决，但有些不能，作为灵活性的代价，其效率会比线段树低一些，而且复杂度算不对会T。

比方说，我们选择l到r区间，这个区间包含了完整的3个大小为size的块，那么我们对这个块的操作通常是O(1)级别的操作。

当然，我们选定的区间通常并非恰好是某些块的端点，也没法将数组正好分成k块每块的都是size大小，所以处理这些边界数据的问题变成了主要的时间耗费。

想要处理起来容易，就需要前期工作准备充分一些。
1.对于块，开一个结构体，存储一个块的内部素，这个块在原数组中的起始于终止下标，这个块的长度，这个块的各种tag，等等信息都可以存储。这样做的好处是对于每一块，块内素处理起来十分方便。
2.对于每个素，我们要预处理其属于那一块。
3.关于块的大小，玄学，，一般情况下如果数组大小为n，求出其sqrt(n)，找到距离sqrt(n)最近的2的幂数就可以了。如果T了可以尝试将块缩小两倍（优先）或者增大两倍。

大体思路

基本都分为两步走
1.如果所查询的区间在一个块的范围内，那么直接暴力遍历从l到r
2.如果跨越多个块，先将整块整块的处理完，再处理边角区间

入门题目

这里主要包括一些基本数列分块题目，第一题由于过于简单所以没用我的模板，第2题到第8题都是模板下来的。第九题因为变化较大，模板不太适合所以没用模板。

这些题目我感觉都很好，作为数列分块的题目来讲，很基础也很全面，难度大概是luogu的绿到蓝

以下题目の测评地址与题目地址

第1题

可以看到，这题需要记录一下区间的累加值，在求值的时候可以直接加上区间的累加值。

先看代码吧。

#include<bits/stdc++.h> using namespace std; const int N=5e4+5; typedef long long ll; int n,len,id[N]; ll a[N],tag[N]; void add(int l,int r,ll c) { 
    int sid=id[l],eid=id[r]; if(sid==eid) for(int i=l;i<=r;i++) a[i]+=c; else { 
    for(int i=l;id[i]==sid;i++) a[i]+=c; for(int i=sid+1;i<eid;i++) tag[i]+=c; for(int i=r;id[i]==eid;i--) a[i]+=c; } } int main() { 
    ll c; scanf("%d",&n); len=sqrt(n); for(int i=1;i<=n;i++) { 
    scanf("%lld",&a[i]); id[i]=(i-1)/len+1; } for(int i=1,opt,x,y;i<=n;i++) { 
    scanf("%d%d%d%lld",&opt,&x,&y,&c); if(!opt) add(x,y,c); else printf("%lld\n",a[y]+tag[id[y]]); } return 0; } 

第2题

这题就是经典的计数问题了，只需要获取每个素当前值然后对比就可以了，是第一个题目的进阶，注意c²需要用longlong表示。

#include<bits/stdc++.h> using namespace std; const int N = 1e5+100; typedef long long ll; ll a[N];//原数组 int along[N];//注册每个素属于那一块 int n; const int block=300;//sqrt(n)块，一块有n/sqrt(n)个 struct node//存储了每一块的起点，终点，长度， { 
    ll st,ed,length,add,num[block+10]; void change(){ 
    for(int i=st;i<=ed;i++)num[i-st+1]=a[i]; sort(num+1,num+length+1); } int ask(ll c) { 
    return lower_bound(num+1,num+length+1,c-add)-num-1; } }b[block]; void upd(int l,int r,int v) { 
    int p=along[l],q=along[r]; if(p==q){ 
    for(int i=l;i<=r;i++)a[i]+=v; b[p].change(); return; } for(int i=p+1;i<=q-1;i++)b[i].add+=v; for(int i=l;i<=b[p].ed;i++)a[i]+=v; for(int i=b[q].st;i<=r;i++)a[i]+=v; b[p].change(); b[q].change(); } int query(int l,int r,ll c) { 
    int ret=0; int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++) if(a[i]+b[p].add<c)ret++; return ret; } for(int i=p+1;i<=q-1;i++)ret+=b[i].ask(c); for(int i=l;i<=b[p].ed;i++) if(a[i]+b[p].add<c)ret++; for(int i=b[q].st;i<=r;i++) if(a[i]+b[q].add<c)ret++; return ret; } signed main() { 
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int t=n/block; if(n%block)t++; for(int i=1;i<=t;i++) { 
    b[i].st=(i-1)*block+1; b[i].ed=i*block; b[i].length=b[i].ed-b[i].st+1; } b[t].ed=n; b[t].length=n-b[t].st+1; for(int i=1;i<=t;i++) { 
    b[i].change(); for(int j=b[i].st;j<=b[i].ed;j++) along[j]=i; } for(int i=1;i<=n;i++) { 
    int op,l,r; ll c; cin>>op>>l>>r>>c; if(op)cout<<query(l,r,c*c)<<'\n'; else upd(l,r,c); } return 0; } 

第3题

题目的修改操作仍为区间加值，

对于整块的区间，查询块内c的前驱，只需要查询比c小的最大值排在第几个就可以了。

对于分散的区间，只需要查询比c小的最大值（打擂台）

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+100; int a[N];//原数组 int along[N];//注册每个素属于那一块 int n; const int block=500;//sqrt(n)块，一块有n/sqrt(n)个 struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的素 { 
    int st,ed,length,add=0ll,num[block+10]; void change(){ 
    for(int i=st;i<=ed;i++)num[i-st+1]=a[i]; sort(num+1,num+length+1); } int ask(int c) { 
    int pos=lower_bound(num+1,num+length+1,c-add)-(num+1); if(!pos) return -1; return num[pos]+add; } }b[block]; void upd(int l,int r,int v) { 
    int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++)a[i]+=v; b[p].change(); return; } for(int i=p+1;i<=q-1;i++)b[i].add+=v; for(int i=l;i<=b[p].ed;i++)a[i]+=v; for(int i=b[q].st;i<=r;i++)a[i]+=v; b[p].change(); b[q].change(); } int query(int l,int r,int c) { 
    int res=-1; int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++) if((a[i]+b[q].add)<c) res=max(res,a[i]+b[p].add); return res; } for(int i=p+1;i<=q-1;i++) { 
    res=max(res,b[i].ask(c)); } for(int i=l;i<=b[p].ed;i++) { 
    if((a[i]+b[p].add)<c) res=max(res,a[i]+b[p].add); } for(int i=b[q].st;i<=r;i++) { 
    if((a[i]+b[q].add)<c) res=max(res,a[i]+b[q].add); } return res; } signed main() { 
    //freopen("in.txt","r",stdin); cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int t=n/block; if(n%block)t++; for(int i=1;i<=t;i++) { 
    b[i].st=(i-1)*block+1; b[i].ed=i*block; b[i].length=b[i].ed-b[i].st+1; } b[t].ed=n; b[t].length=n-b[t].st+1; for(int i=1;i<=t;i++) { 
    b[i].change(); for(int j=b[i].st;j<=b[i].ed;j++) along[j]=i; } for(int i=1;i<=n;i++) { 
    int op,l,r; int c; cin>>op>>l>>r>>c; if(op) { 
    cout<<query(l,r,c)<<'\n'; } else upd(l,r,c); } return 0; } 

第4题

我们记录区间的sum标记，和add标记，分别代表：目前的和，待加数。那么对于一个整块的区间的区间和就是sum+add*block

对于分散的区间自然逐个加和即可。

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+100; int a[N];//原数组 int along[N];//注册每个素属于那一块 int n; const int block=300;//sqrt(n)块，一块有n/sqrt(n)个 struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的素 { 
    int st,ed,length,add=0,num[block+10],sum=0; void change() { 
    for(int i=st;i<=ed;i++) { 
    sum+=(a[i]-num[i-st+1]); num[i-st+1]=a[i]; } } int ask(int c) { 
    int pos=lower_bound(num+1,num+length+1,c-add)-(num+1); if(!pos) return -1; return num[pos]+add; } }b[block]; void upd(int l,int r,int v) { 
    int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++)a[i]+=v; b[p].change(); return; } for(int i=p+1;i<=q-1;i++)b[i].add+=v; for(int i=l;i<=b[p].ed;i++)a[i]+=v; for(int i=b[q].st;i<=r;i++)a[i]+=v; b[p].change(); b[q].change(); } int query(int l,int r,int c) { 
    int res=0; int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++) { 
    res=(res+a[i]+b[p].add)%c; } return res; } for(int i=p+1;i<=q-1;i++) { 
    res=(res%c+b[i].sum%c+b[i].add*block%c)%c; } for(int i=l;i<=b[p].ed;i++) { 
    res=(res+a[i]+b[p].add)%c; } for(int i=b[q].st;i<=r;i++) { 
    res=(res+a[i]+b[q].add)%c; } return res%c; } signed main() { 
    //freopen("in.txt","r",stdin); cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int t=n/block; if(n%block)t++; for(int i=1;i<=t;i++) { 
    b[i].st=(i-1)*block+1; b[i].ed=i*block; b[i].length=b[i].ed-b[i].st+1; } b[t].ed=n; b[t].length=n-b[t].st+1; for(int i=1;i<=t;i++) { 
    b[i].change(); for(int j=b[i].st;j<=b[i].ed;j++) along[j]=i; } for(int i=1;i<=n;i++) { 
    int op,l,r; int c; cin>>op>>l>>r>>c; if(op) { 
    cout<<query(l,r,c+1)<<'\n'; } else upd(l,r,c); } return 0; } 

第5题

关键在于更新操作上。

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+100; int a[N];//原数组 int along[N],vis[N];//注册每个素属于那一块 int n; const int block=300;//sqrt(n)块，一块有n/sqrt(n)个 struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的素 { 
    int st,ed,length,num[block+10],sum=0ll,id; }b[block]; void upd(int l,int r,int v) { 
    int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++) { 
    if(a[i]>1) { 
    b[q].sum-=a[i]; a[i]=sqrt(a[i]); b[q].sum+=a[i]; } } return; } for(int i=p+1;i<=q-1;i++) { 
    if(vis[i]) { 
    for(int j=b[i].st;j<=b[i].ed;j++) { 
    if(a[j]>1) { 
    b[i].sum-=a[j]; a[j]=sqrt(a[j]); b[i].sum+=a[j]; } } if(b[i].sum==b[i].length) vis[i]=0; } } for(int i=l;i<=b[p].ed;i++) { 
    if(a[i]>1) { 
    b[p].sum-=a[i]; a[i]=sqrt(a[i]); b[p].sum+=a[i]; } } for(int i=b[q].st;i<=r;i++) { 
    if(a[i]>1) { 
    b[q].sum-=a[i]; a[i]=sqrt(a[i]); b[q].sum+=a[i]; } } } int query(int l,int r) { 
    int res=0; int p=along[l],q=along[r]; if(p==q) { 
    for(int i=l;i<=r;i++) res+=a[i]; return res; } for(int i=p+1;i<=q-1;i++) { 
    res+=b[i].sum; } for(int i=l;i<=b[p].ed;i++) { 
    res+=a[i]; } for(int i=b[q].st;i<=r;i++) { 
    res+=a[i]; } return res; } signed main() { 
    //freopen("in.txt","r",stdin); cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) { 
    cin>>a[i]; } int t=n/block; if(n%block)t++; for(int i=1;i<=t;i++) { 
    b[i].st=(i-1)*block+1; b[i].ed=i*block; b[i].length=b[i].ed-b[i].st+1; vis[i]=1; } b[t].ed=n; b[t].length=n-b[t].st+1; for(int i=1;i<=t;i++) { 
    for(int j=b[i].st;j<=b[i].ed;j++) { 
    b[i].sum+=a[j]; along[j]=i; } } for(int i=1;i<=n;i++) { 
    int op,l,r; int c; cin>>op>>l>>r>>c; if(op) { 
    cout<<query(l,r)<<'\n'; } else upd(l,r,c); } return 0; } 

第6题

双修改，这里就和线段树的双tag很像了。要考虑不同修改的优先值和相互之间的影响。

而且，这个题因为双修改，目前的值如果变动必须要把附加在当前值上的操作都做完才行，也就是对应的pushdown操作，有兴趣的可以用分块去挑战一下luogu上的“扶苏的问题”

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+100; const int mod= 1e4+7; int a[N];//原数组 int along[N];//注册每个素属于那一块 int n; const int block=400;//sqrt(n)块，一块有n/sqrt(n)个 struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的素 { 
    int st,ed,length,add=0ll,ploy=1ll,num[block+10],sum=0; }b[block]; void down(int k) { 
    for(int i=b[k].st;i<=b[k].ed;i++) a[i]=(a[i]*b[k].ploy+b[k].add)%mod; b[k].ploy=1ll;b[k].add=0ll; } void upd_add(int l,int r,int v) { 
    int p=along[l],q=along[r]; if(p==q) { 
    down(p); for(int i=l;i<=r;i++) a[i]=(a[i]+v)%mod; return; } down(p);down(q); for(int i=p+1;i<=q-1;i++) b[i].add=(b[i].add+v)%mod; for(int i=l;i<=b[p].ed;i++) a[i]=(a[i]+v)%mod; for(int i=b[q].st;i<=r;i++) a[i]=(a[i]+v)%mod; } void upd_ploy(int l,int r,int v) { 
    int p=along[l],q=along[r]; if(p==q) { 
    down(p); for(int i=l;i<=r;i++) a[i]=a[i]*v%mod; return ; } down(p);down(q); for(int i=p+1;i<=q-1;i++) { 
    b[i].ploy=b[i].ploy*v%mod; b[i].add=b[i].add*v%mod; } for(int i=l;i<=b[p].ed;i++) a[i]=a[i]*v%mod; for(int i=b[q].st;i<=r;i++) a[i]=a[i]*v%mod; return ; } int query(int r) { 
    int p=along[r]; return a[r]*b[p].ploy+b[p].add; } signed main() { 
    //freopen("in.txt","r",stdin); cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int t=n/block; if(n%block)t++; for(int i=1;i<=t;i++) { 
    b[i].st=(i-1)*block+1; b[i].ed=i*block; b[i].length=b[i].ed-b[i].st+1; } b[t].ed=n; b[t].length=n-b[t].st+1; for(int i=1;i<=t;i++) { 
    for(int j=b[i].st;j<=b[i].ed;j++) along[j]=i; } for(int i=1;i<=n;i++) { 
    int op,l,r; int c; cin>>op>>l>>r>>c; if(op==0) { 
    upd_add(l,r,c); } else if(op==1) { 
    upd_ploy(l,r,c); } else { 
    cout<<query(r)%mod<<endl; } } return 0; } 

第7题

同样是目前值修改需要考虑之前的影响。也有可以不考虑的巧妙写法，读者可以挑战一下。

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+100; const int sp= 1e10+7; int a[N];//原数组 int along[N];//注册每个素属于那一块 int n; int vis[N]; const int block=400;//sqrt(n)块，一块有n/sqrt(n)个 struct node//存储了每一块的起点，终点，长度，这个区间被加了多少值，区间内的素 { 
    int st,ed,length,vis=0ll,num[block+10],bec; }b[block]; void down(int k) { 
    if(b[k].vis) for(int i=b[k].st;i<=b[k].ed;i++) a[i]=b[k].bec; b[k].vis=0; } int upd_query(int l,int r,int c) { 
    int p=along[l],q=along[r]; int ans=0ll; if(p==q) { 
    down(p); for(int i=l;i<=r;i++) { 
    ans+=(a[i]==c); a[i]=c; } return ans; } down(p);down(q); for(int i=p+1;i<=q-1;i++) { 
    if(b[i].vis) ans+=((b[i].bec==c)*b[i].length); else for(int j=b[i].st;j<=b[i].ed;j++) ans+=(a[j]==c); b[i].vis=1,b[i].bec=c; } for(int i=l;i<=b[p].ed;i++) { 
    ans+=(a[i]==c); a[i]=c; } for(int i=b[q].st;i<=r;i++) { 
    ans+=(a[i]==c); a[i]=c; } return ans; } signed main() { 
    //freopen("in.txt","r",stdin); cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int t=n/block; if(n%block)t++; for(int i=1;i<=t;i++) { 
    b[i].st=(i-1)*block+1; b[i].ed=i*block; b[i].length=b[i].ed-b[i].st+1; } b[t].ed=n; b[t].length=n-b[t].st+1; for(int i=1;i<=t;i++) { 
    for(int j=b[i].st;j<=b[i].ed;j++) along[j]=i; } for(int i=1,c,l,r;i<=n;i++) { 
    cin>>l>>r>>c; cout<<upd_query(l,r,c)<<'\n'; } return 0; } 

第8题

这题和之前的题思路上有根本的不同，需要预处理一个dp[i][j]表示第i块到第j块的众数。
具体操作看代码大概就能懂了。

#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e5+100; const int block=100; const int NN= 1e3+100; int n,id,v[N],belong[N],dp[NN][NN];//第i块到第j块的众数。 map<int,int>mp; int val[N],cnt[N]; vector<int>ve[N]; void pre(int x) { 
    memset(cnt,0,sizeof(cnt)); int mx=0,ans=0; for(int i=(x-1)*block+1;i<=n;i++) { 
    cnt[v[i]]++; if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans])) { 
    ans=v[i]; mx=cnt[v[i]]; } dp[x][belong[i]]=ans; } } int query(int l,int r,int x)//求出在l到r范围内有几个ans { 
    int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l); return t; } int query(int a,int b) { 
    int ans=0,mx=0; ans=dp[belong[a]+1][belong[b]-1]; mx=query(a,b,ans); for(int i=a;i<=min(belong[a]*block,b);i++) { 
    int t=query(a,b,v[i]); if(t>mx||(t==mx&&val[v[i]]<val[ans])) { 
    ans=v[i]; mx=t; } } if(belong[a]!=belong[b]) for(int i=(belong[b]-1)*block+1;i<=b;i++) { 
    int t=query(a,b,v[i]); if(t>mx||(t==mx&&val[v[i]]<val[ans])) { 
    ans=v[i]; mx=t; } } return ans; } signed main() { 
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++) { 
    cin>>v[i]; if(!mp[v[i]]) { 
    mp[v[i]]=++id; val[id]=v[i]; } v[i]=mp[v[i]]; ve[v[i]].push_back(i); } for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1; for(int i=1;i<=belong[n];i++) pre(i); for(int i=1,a,b;i<=n;i++) { 
    cin>>a>>b; if(a>b) swap(a,b); cout<<val[query(a,b)]<<endl; } return 0; } 

入门共9题，有一题未展示，共写了52发之后全A。