学妹让我教她分块，翻了翻以前的一篇博客，发现写的太难、太简略了，所以写了这篇博客 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 呢

写了这么多字，这部分先咕着吧，以后有时间再写（