学妹让我教她分块，翻了翻以前的一篇博客，发现写的太难、太简略了，所以写了这篇博客 QAQ。
真的是分块最基础的教程，大佬可以跳过了。
如果本文有可以改进的地方，可以在评论区提出。
前言 - 序列分块是什么
顾名思义，序列分块就是把数列分成若干小块进行处理和维护，我们会把每一块当成整体，维护这些整体的有关信息。
最基础的分块当取块长为 时的初始化复杂度是
，单次操作复杂度是
，当然一些较为复杂的题需要对照题目具体分析。
例题一 - P3372 【模板】线段树 1
简要分析
区间加区间和，参考题目名称可以发现，出题人貌似想让我们写线段树，于是我们考虑如何不写线段树。我们采用分块。
变量定义
以下是代码中的一些数组或变量名称及其含义：
-
：数列长度和操作次数。
-
：数列第
项。
-
：第
-
：第
-
：数列第
-
：第
-
：第
-
：块长。
-
：总块数。
块状数组初始化
首先取块长为 ，然后枚举每一块，可以知道第
块的左端点是第
块的右端点的下一个元素，第
块的右端点是
，我们通过这个式子对
进行初始化。
随后枚举 的所有元素，用
记录他们的和，同时把这些元素的
标记为
。
至此，我们便完成了初始化，因为每一块的区间不重叠且没有遗漏， 数组的每个元素下标恰好访问一遍，因此复杂度是
的。
此部分代码：
void initBlock() {
sz = sqrt(n);
while(++tot) {
L[tot] = R[tot-1] + 1;
R[tot] = min(sz*tot, n);
rep(i, L[tot], R[tot]) pos[i] = tot, s[tot] += a[i];
if(R[tot] == n) break;
}
}
区间加
此部分操作要求将 的所有数加上
，暴力单次加是
的，显然需要优化。
对于 与
在同一块的情况，我们暴力从
枚举到
，将
和
加上
。由于块长为
，因此暴力枚举这一部分的复杂度为
。
对于不在同一块的情况，对两侧的零散块（不完整块，即 所在块）按照同上的方法暴力处理，对中间的每个完整块记录整体加法标记
，并把块中所有数和同步记录。由于块长为
，不完整块最多操作次数为
，完整块不超过
个，因此这一部分的复杂度为
。
综上，块状数组区间加法的复杂度为 。
此部分代码：
void modify(ll x, ll y, ll delta) {
ll l = pos[x], r = pos[y];
if(l == r) rep(i, x, y) a[i] += delta, s[l] += delta;
else {
rep(i, x, R[l]) a[i] += delta, s[l] += delta;
rep(i, l+1, r-1) tag[i] += delta, s[i] += delta * (R[i] - L[i] + 1);
rep(i, L[r], y) a[i] += delta, s[r] += delta;
}
}
区间和
查询区间 所有数的和，同样不能暴力加，考虑按照同样的方法优化：
对于同一块的情况，暴力枚举并累加 ，注意不要漏掉当前块的整体加法标记！
对于不在同一块的情况，两侧的零散块同样方法处理，中间的整块直接累加块和即可。
同样的，查询区间和的复杂度为 。
此部分代码：
ll query(ll x, ll y) {
ll l = pos[x], r = pos[y], ans = 0;
if(l == r) rep(i, x, y) ans += a[i] + tag[l];
else {
rep(i, x, R[l]) ans += a[i] + tag[l];
rep(i, l+1, r-1) ans += s[i];
rep(i, L[r], y) ans += a[i] + tag[r];
}
return ans;
}
AC 本题
将以上代码结合起来即可 AC 本题，总复杂度为 ，完整代码戳我。
习题一 - P2357 守墓人
基本上是双倍经验，可以稍加修改通过本题。
例题二 - P2801 教主的魔法
简要分析
简要题意：区间加，查询区间内多少个数大于等于 。
我们可以采用分块，对每一块进行重构排序，然后询问时直接使用二分。
块内排序
块内排序在代码中用的比较多，因此我专门写了个函数重构块。
void reconstruct(int x) {
rep(i, L[x], R[x]) b[i] = a[i];
sort(b+L[x], b+1+R[x]);
}
初始化
初始化部分主要有一个更改：对于每一块，需要将该块内元素拷贝一遍并排序。
新初始化复杂度 ，使用对数换底公式可以知道这个复杂度与
相差为常数，可以视为
。
区间加
区间加对零散块直接暴力加，然后进行重构；因为对整块的加法不改变块内元素顺序，打上整体加法标记即可。
复杂度 。
区间大于等于 
数个数
零散块直接暴力查询，记得加上整体加法标记。
对于完整块，在排好序的块内二分找 ，因为是排好序的，直接根据下标算即可。
复杂度 。
AC 本题
结合一下以上部分即可 AC 本题，总复杂度为 。看到数据范围
是比较小的，可以通过。
习题二 - U147831 分块问题 3
区间加，求区间内 的前驱。
依然是块内排序、查询时二分的思想。
习题三 - U147840 分块问题 6
单点插入，单点查询。
对于每一块维护 vector，插入时遍历每一块找插入点，查询时遍历每一块用 vector 查值即可。
这一方法可以通过本题，但是因为插入的数随机生成，每一块的插入次数大致均匀。可以通过构造数据的方式卡掉这一做法。
我选择当一块的 vector 大小超过 的时候将所有 vector 清空并重构，因为重构的次数比较少可以通过本题。
习题四 - P4145 上帝造题的七分钟 2 / 花神游历各国
区间开平方根，区间和。
与线段树做法想法类似，维护每一块的最小值。
习题五 - U147877 分块问题 8
查询区间内多少个数为 ，并把区间改为
。
经过我和几个初二学长的探讨，本题珂朵莉树解法的复杂度没有问题。
但是毕竟是练习分块，我还是老老实实地写了分块。
大致想法就是，对每一块记录区间赋值标记，优先级高于每个数的值，初始区间赋值标记设置一个特殊值表示不存在。其他的就比较基础了。
习题六 - P4168 [Violet]蒲公英
这题貌似被我咕了好久，到现在都没做。。。
先放在这里吧，有时间做完再补上（（（
挑战 - 学分块怎么能不做 Ynoi 呢
写了这么多字，这部分先咕着吧，以后有时间再写（
网友评论