Pt.1: 分块是什么
其实，分块是一种思想，而不是一个数据结构。
分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
——摘自OI Wiki
谈谈我个人的理解吧。分块就是把原数据分成一个个块，然后在处理问题的时候对块进行操作而非对一个个数据进行操作，以此来取得更高的效率。
打个比方，分块就是将一堆数据打包起来，然后对包裹进行操作，这样相较于对一个个数据操作显然会更快。
Pt.2: 分块的应用
分块可以将 对一个个数据进行操作(增删改查) 这类的操作的效率进行优化。
很自然地就可以联想到区间修改，查询等操作。
分块相较于线段树这类功能强大的数据结构的优点是容易理解，代码量小，方便调试。缺点是效率较低。还可以用来打暴力。
我们来看一个分块的典型应用吧。
solution
这道题是分块的模板题，简单的区间修改与单点查询。
我们将原数据分为一个个块,id[i]表示数据i所在块的编号。
修改操作：
对于每个区间，区间里的整块我们整个整个的操作，但是区间的长度不保证里面都是完整的块，两边可能会有余。对于两边的余，我们直接暴力修改即可。
void update(int l,int r,int x){//l~r里的数都增加xif(id[l]==id[r]){//l和r在同一个块里也就是中间没有整块，直接暴力for(int i=l;i<=r;i++){a[i]+=x;s[id[i]]+=x;}return;}for(int i=l;id[i]==id[l];i++)a[i]+=x,s[id[l]]+=x;//两边有余，暴力修改for(int i=id[l]+1;i<=id[r]-1;i++)up[i]+=x,s[i]+=x*blen;//up数组相当于懒标记，对于整个块的区间加/减可以直接操作up数组，避免时间复杂度退化for(int i=r;id[i]==id[r];i--)a[i]+=x,s[id[r]]+=x;
}
查询操作：
和修改一样。大块直接查一整块，小的暴力。
另外，题目要求是单点查询，实际上就是l=r的特殊情况，可以合并在一起处理。
int query(int l,int r){//查询区间l到r的和int res=0;if(id[l]==id[r]){for(int i=l;i<=r;i++){res+=a[i]+up[id[l]];}return res;}for(int i=l;id[i]==id[l];i++)res+=a[i]+up[id[i]];for(int i=id[l]+1;i<=id[r]-1;i++)res=res+s[i];for(int i=r;id[i]==id[r];i--)res+=a[i]+up[id[i]];return res;
}
现在解决了查询和修改的问题。但是最大的问题来了，该怎么分块呢？
我们可以用一个固定的块长分块，余数则单独分另一个块。
根据均值不等式可以推出，$ \sqrt n $是最佳的块长。
于是我们的分块就做完了，查询的时间复杂度为$ O(\sqrt n)$,修改一样。
总的时间复杂度为$ O(n \sqrt n) $。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300005;
int n,a[N],opt,l,r,c,blen,id[N],s[N],up[N];
void update(int l,int r,int x){if(id[l]==id[r]){for(int i=l;i<=r;i++){a[i]+=x;s[id[i]]+=x;}return;}for(int i=l;id[i]==id[l];i++)a[i]+=x,s[id[l]]+=x;for(int i=id[l]+1;i<=id[r]-1;i++)up[i]+=x,s[i]+=x*blen;for(int i=r;id[i]==id[r];i--)a[i]+=x,s[id[r]]+=x;
}
int query(int l,int r){int res=0;if(id[l]==id[r]){for(int i=l;i<=r;i++){res+=a[i]+up[id[l]];}return res;}for(int i=l;id[i]==id[l];i++)res+=a[i]+up[id[i]];for(int i=id[l]+1;i<=id[r]-1;i++)res=res+s[i];for(int i=r;id[i]==id[r];i--)res+=a[i]+up[id[i]];return res;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;blen=sqrt(n);//blen保存块长for(int i=1;i<=n;i++){cin>>a[i];id[i]=(i-1)/blen+1;//块长计算公式s[id[i]]+=a[i];}while(n--){cin>>opt;if(opt==0){cin>>l>>r>>c;update(l,r,c);}else{cin>>l>>r>>c;cout<<query(r,r)<<'\n';}}return 0;
}
Pt.3：例题
1.
P13979 数列分块入门 4
题目描述
给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，区间求和。
输入格式
第一行输入一个数字 \(n\)。
第二行输入 \(n\) 个数字，第 \(i\) 个数字为 \(a_i\)，以空格隔开。
接下来输入 \(n\) 行询问，每行输入四个数字 \(\mathrm{opt}\)、\(l\)、\(r\)、\(c\)，以空格隔开。
若 \(\mathrm{opt} = 0\)，表示将位于 \([l, r]\) 的之间的数字都加 \(c\)。
若 \(\mathrm{opt} = 1\)，表示询问位于 \([l, r]\) 的所有数字的和 \(\bmod (c+1)\)。你需要输出非负的余数值。
输出格式
对于每次询问，输出一行一个数字表示答案。
输入输出样例 #1
输入 #1
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
输出 #1
1
4
说明/提示
子任务
子任务 1（40 分）：\(1 \leq n \leq 50000, -2^{31} \leq a_i,c \leq 2^{31}-1\)。
子任务 2（60 分）：\(1 \leq n \leq 3\times 10^5, -2^{31} \leq a_i,c \leq 2^{31}-1\)。
对于所有测试数据，满足 \(1 \leq n \leq 3\times 10^5, -2^{31} \leq a_i,c \leq 2^{31}-1\)。\(1 \leq l \leq r \leq n\)。\(\mathrm{opt} \in \{0,1\}, 1 \leq l \leq r\leq n\)。每次操作后的 \(a_i\) 满足 \(-2^{31} \leq a_i \leq 2^{31}-1\)。特别地，数据保证当 \(\mathrm{opt}=1\) 时，\(c\geq 0\)。
solution
思路其实没啥，就是上面的板子把主函数里的区间查询改一下即可。
要注意的是取模的问题，因为取模运算常数较大，再加上有些地方我们是不需进行取模操作的，所以我们可以适当的省去一些取模的地方一次来达到优化常数的目的。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300005;
int n,a[N],l,r,c,blen,id[N],s[N],up[N];
bool opt;
void update(int l,int r,int x){if(id[l]==id[r]){for(int i=l;i<=r;i++){a[i]+=x;s[id[i]]+=x;}return;}for(int i=l;id[i]==id[l];i++)a[i]+=x,s[id[l]]+=x;for(int i=id[l]+1;i<=id[r]-1;i++)up[i]+=x,s[i]+=x*blen;for(int i=r;id[i]==id[r];i--)a[i]+=x,s[id[r]]+=x;
}//以上全部不取模
int query(int l,int r,int mod){int res=0;if(id[l]==id[r]){for(int i=l;i<=r;i++){res+=a[i]+up[id[l]];res%=mod;}return res;}for(int i=l;id[i]==id[l];i++)res+=a[i]+up[id[i]];for(int i=id[l]+1;i<=id[r]-1;i++)res=res+s[i];//上面两行不取模for(int i=r;id[i]==id[r];i--)res+=a[i]+up[id[i]],res%=mod;return res;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;blen=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];id[i]=(i-1)/blen+1;s[id[i]]+=a[i];}while(n--){cin>>opt;if(opt==0){cin>>l>>r>>c;update(l,r,c);}else{cin>>l>>r>>c;cout<<(query(l,r,c+1)+c+1)%(c+1)<<'\n';}}return 0;
}
2.
P1503 鬼子进村
题目背景
小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。
题目描述
县城里有 \(n\) 个用地道相连的房子，第 \(i\) 个只与第 \(i-1\) 和第 \(i+1\) 个相连。特别的，第 \(1\) 个房子只和第 \(2\) 个联通，第 \(n\) 个房子只和第 \(n-1\) 个联通。这时有 \(m\) 个消息依次传来：
-
若消息为
D x：鬼子将 \(x\) 号房子摧毁了，地道被堵上。 -
若消息为
R：村民们将鬼子上一个摧毁的房子修复了。 -
若消息为
Q x：有一名士兵被围堵在 \(x\) 号房子中。
现定义能够到达如下：若存在房子 \(i,j(1\leq i\leq j\leq n)\)，使得对于任意的 \(k(i\leq k\leq j)\) 都满足房子 \(k\) 未被摧毁，则称房子 \(i\) 与房子 \(j\) 互相能够到达。
李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。
输入格式
第一行两个整数 \(n,m\)。
接下来 \(m\) 行，有如题目所说的三种信息共 \(m\) 条。
输出格式
对于每一个被围堵的士兵，输出该士兵能够到达的房子数。
输入输出样例 #1
输入 #1
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4输出 #1
1
0
2
4说明/提示
\(1\leq n,m\leq 5\times 10^4\)。
若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。
solution
对每个房子进行分块，用一个 cnt 数组记录块内房子被摧毁的个数，如果 cnt[i]==0 则可以直接跳过 i 这个块，以此来用分块对查询进行加速。
如何实现建房子/炸房子？对于每个被炸的房子，将其放入栈中，在修复时弹出栈顶，对栈顶进行操作即可。和普通分块相似。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50005;
int n,m,a[N],x,blen,id[N],s[N],up[N],stk[N],tp;
char opt;
int find_l(int x){int lb=(id[x]-1)*blen+1;for(int i=x-1;i>=lb;i--)if(!a[i])return i;for(int b=id[x]-1;b>=1;b--){if(!s[b])continue;int rb=min(b*blen,n);for(int i=rb;i>=(b-1)*blen+1;i--)if(!a[i])return i;}return 0;
}
int find_r(int x){int rb=min(id[x]*blen,n);for(int i=x+1;i<=rb;i++)if(!a[i])return i;int t=(n-1)/blen+1;for(int b=id[x]+1;b<=t;b++){if(!s[b])continue;int lb=(b-1)*blen+1;for(int i=lb;i<=min(b*blen,n);i++)if(!a[i])return i;}return n+1;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;blen=sqrt(n);for(int i=1;i<=n;i++){a[i]=1;id[i]=(i-1)/blen+1;}while(m--){cin>>opt;if(opt=='D'){cin>>x;if(a[x])a[x]=0,s[id[x]]++,stk[++tp]=x;}else if(opt=='R'){if(tp){x=stk[tp--];a[x]=1;s[id[x]]--;}}else{cin>>x;if(!a[x]){ cout<<0<<'\n'; continue; }cout<<find_r(x)-find_l(x)-1<<'\n';}}return 0;
}
Pt.4: 莫队是什么
假设 \(n=m\)，那么对于序列上的区间询问问题，如果从 \([𝑙,𝑟]\)的答案能够 \(𝑂(1)\) 扩展到 \([𝑙−1,𝑟],[𝑙+1,𝑟],[𝑙,𝑟+1],[𝑙,𝑟−1],[l-1,r],[l+1,r],[l,r+1],[l,r-1]\)（即与 \([l,r]\) 相邻的区间）的答案，那么可以在 \(O(n\sqrt n)\) 的复杂度内求出所有询问的答案。
——摘自OI Wiki
在我看来，莫队是一个很暴力的算法。
谈谈我自己的看法吧。莫队就是对于一些区间问题，将所有的操作进行排序，然后对于两个操作直接\(O(1)\)延伸到相邻区间，直到从上一个操作拓展/收缩到下一个操作。
Pt.5: 如何莫队？
莫队最重要的部分有二，一个是排序，另一个是\(O(1)\)拓展/收缩的过程。
拓展/收缩要对题思考，不同的题操作也不同，这里不过多赘述。
至于排序嘛，一般的排序方法要用到上面的分块。我们记录好每个点所在块的编号，对于每个区间\([l,r]\)，以 l 所在块的编号为第一关键字，以r所在块的编号为第二关键字。
每次查询的时间复杂度按块长决定。令块长为blen，q个查询，则时间复杂度为\(O(q\sqrt blen)\)。
也许你认为莫队到这里就结束了，其实不止。朴素莫队的排序方式并不是最优的，指针移动会有很多冗余。我们可以采用奇偶化排序，即对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序。这样r指针在处理完奇数块的查询后，返回时会顺便把偶数块的查询也解决，大大减少了指针移动的次数。在采用奇偶化排序后，莫队算法的效率大约会快30%。
Pt.5: 例题
solution
莫队板子题。我们只需要维护一个桶保存一个属在区间\([L,R]\)内的出现次数，然后相对应的去维护答案即可。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
struct Q{int l,r,id;}q[N];
int n,m,k,B,a[N],cnt[N],cur,ans[N];
bool cmp(const Q&a,const Q&b){int ba=a.l/B,bb=b.l/B;if(ba!=bb)return ba<bb;return (ba&1)?(a.r<b.r):(a.r>b.r);
}
void add(int x){cur+=2*cnt[a[x]]+1;cnt[a[x]]++;}
void del(int x){cnt[a[x]]--;cur-=2*cnt[a[x]]+1;}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>k;B=max(1,(int)(n/sqrt(m)));for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;sort(q+1,q+m+1,cmp);int L=1,R=0;for(int i=1;i<=m;i++){while(L>q[i].l)add(--L);while(R<q[i].r)add(++R);while(L<q[i].l)del(L++);while(R>q[i].r)del(R--);ans[q[i].id]=cur;}for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';return 0;
}