我们将一个数组分为一个个长度为 $B$ 的块，并且维护块间信息，这个思想就叫做分块。

分块有常数小、好想、适用性高的特点，但根号复杂度是分块的硬伤。

分块是一种暴力，但是不失为暴力中最优雅的。它可以维护一些传统数据结构无法维护的信息，这点在例题中将会体现。如果有恰当的实现方式，它可以以相当快的运行速度碾压标算。

主要内容

一个长度为 $n$ 的数列 ${a_n}$，可以被分成多个长度为 $B$ 的块。

比如我有一个 $n=20$ 的数列，$B=5$，那么就有以下块：

• $[1, 5]$。
• $[6, 10]$。
• $[11, 15]$
• $[16,20]$。

如果我们并无法做到 $B\mid n$， 那么也没关系，只要保证最后一块的末尾是 $n$ 即可。

符号约定

• $B$，块长。
• $\mathrm{bl}_i$，数组，块 $i$ 的起始点。
• $\mathrm{br}_i$，数组，块 $i$ 的终点。
• $\mathrm{bel}_i$，数组，原序列上第 $i$ 个位置所属块的编号。

查询和维护信息的方式

对于每一次查询 $[l, r]$，分类讨论：

• 如果 $l$ 和 $r$ 在同一块内，暴力查询，复杂度 $\mathcal{O}(B)$ 。
• 如果 $l$ 和 $r$ 在相邻块，依旧暴力查询（对于某些设计了前后缀信息的数据结构，可以做到 $\mathcal{O}(1)$），复杂度 $\mathcal{O}(B)$。
• 如果都不在同一块，那么先把区间上的整块处理了，一个块常数复杂度处理（这个基于预处理的块间信息），复杂度是 $\mathcal{O}(n/B)$，而对于 $l$ 到 $\mathrm{br}_l$、$\mathrm{bl}_r$ 到 $r$ 的部分，暴力处理，复杂度 $\mathcal{O}(n/B+B)$。

综上，查询部分复杂度为 $\mathcal{O}\left(m\left(\dfrac{n}{B}+B\right)\right)$。而对于修改也是同理。

最优的复杂度

可以证明，对于最坏情况，$B=\sqrt{n}$ 时最优。这个用初中数学就能证明出来。感性地理解，要让 $n/B$ 和 $B$ 均衡，所以最好的块长方案是 $n/B=B$，这种情况下就有 $B=\sqrt{n}$。

当然，对于部分操作，可能在单一块操作上有大常数，也可能在整块处理上有大常数，这时候 $B=\sqrt{n}$ 就不再是最佳方案，要视情况调整。

下面给一些例题，需要传送的点击题目名称即可传送到原题。在这些题目中，很多的 $n$ 不仅作为序列长度，也作为查询次数，因此它们也可以用莫队高效地做出。

例题 1：P13976 数列分块 1

省流：区间加，单点查。

$1\le n \le 3\times 10^5$。

Sol

这很显然是个 BitTree 板子题，使用 BitTree 可以快速地在 $\mathcal{O}((m+n)\log n)$ 完成操作。但现在想想分块怎么做。设 $B=\sqrt{n}$。

对于修改，散块就直接暴力在原数组上执行区间加，考虑整块怎么做。

设计一个懒惰标记 $\mathrm{lazy}_i$，表示第 $i$ 块作为整块被执行区间加的历史和（没错这个和线段树的懒标记是一个东西）。这样就能在常数复杂度下修改整块。

对于查询，将它在原序列的值加上它所属块的懒标记的值，就是答案了。

代码很好写，如下：

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {
    
}

#define int ll
int arr[300005], tag[300005];
int fkl[300005], fkr[300005], fkcnt = 0, n;

int findk(int x) {
    rep(i, 1, fkcnt) {
        if (fkl[i] <= x && x <= fkr[i]) return i;
    }
    return fkcnt;
}

main() {
    cin >> n;
    rep(i, 1, n) cin >> arr[i];
    int cn = 0, BLK = sqrt(n);
    while (cn < n) {
        fkl[++fkcnt] = cn + 1;
        cn += BLK;
        fkr[fkcnt] = min(cn, n);
    }
    if (cn < n)
        fkl[++fkcnt] = cn + 1, fkr[fkcnt] = n;
    while (n--) {
        int typ, l, r, c;
        cin >> typ >> l >> r >> c;
        if (typ == 0) {    
            int lk = findk(l), rk = findk(r);
            rep(i, lk + 1, rk - 1) tag[i] += c;
            rep(i, l, min(r, fkr[lk])) arr[i] += c;
            if (fkl[rk] > l)
                rep(i, fkl[rk], r) arr[i] += c;
        } else {
            ll ans = tag[findk(r)] + arr[r];
            cout << ans << '\n';
        }
    }
//    int t; cin >> t; while (t--) solve();
    return 0;
}

例题 2：P2801 教主的魔法

其实这里有个数列分块 2，基本一样。

那为什么我没放分块 2 呢？因为鄙人能力有限分块 2 没卡过常，做不出来。

不说闲话了，给题面：

省流：区间加，区间查询不小于 $c$ 的值的个数。

$n\le 10^6$。

Sol

那……这个怎么做啊？

如果是传统数据结构，我们会考虑建树套树，树状数组套一个主席树，维护修改操作，以及区间查询操作（方法是在上面做整体二分）。

但这种问题就连树套树也力不从心，区间修改不就炸了吗，况且 2log 复杂度加上 $32$ 倍常数，那不得被卡爆啊！

所以我们考虑使用分块。维护以下两个数组：

• $\mathrm{lazy}_i$，懒标记。
• $\mathrm{sorted}_{b,i}$ 第 $b$ 块内升序排序后的第 $i$ 个元素。

修改操作：散块暴力修改，修改后更新 sorted 数组。整块改懒标记。

查询操作：散块暴力查询（别忘了加懒标记），整块在 sorted 数组内二分，求最小的满足 $\mathrm{sorted}_{b,p}+ \mathrm{lazy}_p\ge c$ 的 $p$，并将块长度减去 $p$ 加上 $1$ 计入答案。

代码也很好写，如下：

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {
    
}

int n, q;
const int N = 1E6 + 5;
int arr[N], B, bel[N], bl[N], br[N];
const int bsz = 1E3 + 5;
int sorted[bsz][bsz], lazy[bsz];

void init() {
    for (int i = 1; i <= bsz; i++) {
        bl[i] = (i - 1) * bsz + 1;
        br[i] = i * bsz;
        if (br[i] >= n) {
            br[i] = n;
            B = i;
            break;
        }
    }
    for (int i = 1; i <= B; i++) {
        for (int j = bl[i]; j <= br[i]; j++) {
            bel[j] = i;
        }
    }
    for (int i = 1; i <= B; i++) {
        for (int j = bl[i]; j <= br[i]; j++) {
            sorted[i][j - bl[i] + 1] = arr[j];
        }    
        sort(sorted[i] + 1, sorted[i] + br[i] - bl[i] + 2);
    }
}

void update(int l, int r, int v) {
    if (bel[l] + 1 >= bel[r]) {
        for (int i = l; i <= r; i++) {
            arr[i] += v;
        }
        for (int i = bel[l]; i <= bel[r]; i++) {
            for (int j = bl[i]; j <= br[i]; j++) {
                sorted[i][j - bl[i] + 1] = arr[j];
            }
            sort(sorted[i] + 1, sorted[i] + br[i] - bl[i] + 2);
        }
        return;
    }
    for (int i = l; i <= br[bel[l]]; i++) {
        arr[i] += v;
    }
    for (int i = bl[bel[r]]; i <= r; i++) {
        arr[i] += v;
    }
    for (int j = bl[bel[l]]; j <= br[bel[l]]; j++) {
        sorted[bel[l]][j - bl[bel[l]] + 1] = arr[j];
    }
    for (int j = bl[bel[r]]; j <= br[bel[r]]; j++) {
        sorted[bel[r]][j - bl[bel[r]] + 1] = arr[j];
    }
    sort(sorted[bel[r]] + 1, sorted[bel[r]] + br[bel[r]] - bl[bel[r]] + 2);
    sort(sorted[bel[l]] + 1, sorted[bel[l]] + br[bel[l]] - bl[bel[l]] + 2);
    for (int i = bel[l] + 1; i < bel[r]; i++) {
        lazy[i] += v;
    }
}

int query(int l, int r, ll v) { 
    int ans = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {
            if (lazy[bel[l]] + arr[i] >= v) ans++;            
        }
        return ans;
    }
    for (int i = l; i <= br[bel[l]]; i++) {
        if (lazy[bel[l]] + arr[i] >= v) ans++;
    }
    for (int i = bl[bel[r]]; i <= r; i++) {
        if (lazy[bel[r]] + arr[i] >= v) ans++;
    }
    for (int i = bel[l] + 1; i < bel[r]; i++) {
        int pos = lower_bound(sorted[i] + 1, sorted[i] + br[i] - bl[i] + 2, v - lazy[i]) - sorted[i];
        ans += br[i] - bl[i] + 1 - pos + 1;
    }
    return ans;
}

main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    init();
    while (q--) {
        char c;
        cin >> c;
        if (c == 'A') {
            int l, r, c;
            cin >> l >> r >> c;
            cout << query(l, r, c)  << '\n';
        } else {
            int l, r, c;
            cin >> l >> r >> c;
            update(l, r, c);
        }
    }
    //    int t; cin >> t; while (t--) solve();
    return 0;
}

复杂度：$\mathcal{O}(n+m\sqrt{n})$。

例题 3：P13984 区间最小众数查询 / P4168 区间众数出现次数查询（强制在线）

我这里只浅谈一下 P13984，亲测只要微调就能通过 P4168，算是双倍经验。

该做法来源于 @sswyhprays 的 P13984 题解，我觉得他讲的更好，我也是看了他的会的。

先离散化，原题数据太大了。后面默认是离散化后的数据。

预处理 $f_{i,j}$ 表示块 $i$ 到块 $j$ 的最小众数。预处理 $g_{i,j}$ 表示到第 $i$ 块，数字 $j$ 出现的次数。

预处理 $g_{i, j}$

在第 $i$ 块内部遍历，遍历到一个数 $t$，就操作 $g_{i,t}\gets g_{i,t} + 1$。之后做一遍前缀和就可以了。

预处理 $f_{i,j}$

在有了 $g_{i,j}$ 的基础上，可以想到：第 $i$ 到第 $j$ 块中数字 $t$ 出现的次数是 $g_{j,t}-g_{i-1,t}$。

处理方法：枚举 $i$。再枚举 $j$，从 $\mathrm{bl}_i$ 枚举到 $n$。然后弄一个桶，用 $g$ 数组查询出现次数，遇到更好的更新。j

查询

简单好搞，注意到无非两种情况：

• 答案为整块众数，即为 $f_{i,j}$。
• 出现在散块中

对于第二种情况，散块暴力存储每个数字的出现次数，整块使用预处理的 $g_{i,t}$ 就可以了。所以我们做完了。

#include <bits/stdc++.h>
using namespace std;

const int N = 3E5 + 5;
const int bsz = sqrt(N);
int B, p[bsz + 100][bsz + 100], n, arr[N], bl[N], br[N], bel[N], s[bsz + 100][N], lsh[N], cnt;
int bucket[N];

void block_init() {
    B = bsz + 95;
    for (int i = 1; i <= B; i++) {
        bl[i] = (i - 1) * bsz + 1;
        br[i] = i * bsz;
        if (br[i] >= n) {
            B = i;
            br[i] = n;
            break;
        }
    }
    for (int i = 1; i <= B; i++) {
        for (int j = bl[i]; j <= br[i]; j++) {
            bel[j] = i;
        }
    }
}

int find(int x) {
    return lower_bound(lsh + 1, lsh + cnt + 1, x) - lsh;
}

int query(int l, int r) {
    bucket[n] = 0;
    int md = n;
    if (bel[l]  + 1 >= bel[r]) {
        for (int i = l; i <= r; i++) {
            md = arr[i];
            bucket[arr[i]] = 0;
        }
        for (int i = l; i <= r; i++) {
            bucket[arr[i]]++;
            if (bucket[arr[i]] > bucket[md] || (bucket[arr[i]] == bucket[md] && arr[i] < md))
                md = arr[i];
        }
        return md;
    }
    md = p[bel[l] + 1][bel[r] - 1];
    int ini = md;
    bucket[md] = s[bel[r] - 1][md] - s[bel[l]][md];
    for (int i = l; i <= br[bel[l]]; i++) {
        if (arr[i] == ini) bucket[md]++;
        else bucket[arr[i]] = s[bel[r] - 1][arr[i]] - s[bel[l]][arr[i]];
    }
    for (int i = bl[bel[r]]; i <= r; i++) {
        if (arr[i] == ini) bucket[md]++;
        else bucket[arr[i]] = s[bel[r] - 1][arr[i]] - s[bel[l]][arr[i]];
    }
    for (int i = l; i <= br[bel[l]]; i++) {
        if (arr[i] == ini) continue;
        bucket[arr[i]]++;
        if (bucket[md] < bucket[arr[i]] || (bucket[md] == bucket[arr[i]] && arr[i] < md))
            md = arr[i];
    }
    for (int i = bl[bel[r]]; i <= r; i++) {
        if (arr[i] == ini) continue;
        bucket[arr[i]]++;
        if (bucket[md] < bucket[arr[i]] || (bucket[md] == bucket[arr[i]] && arr[i] < md))
            md = arr[i];
    }
    return md;
}

void init() {
    for (int bid = 1; bid <= B; bid ++ ) 
        for (int i = bl[bid]; i <= br[bid]; i++)
            for (int lst = bid; lst <= B; lst++)
                s[lst][arr[i]]++;
    
    for (int fr = 1; fr <= B; fr++) {
        int md = n;
        bucket[md] = 0;
        for (int j = bl[fr]; j <= n; j++)
            bucket[arr[j]] = 0;

        for (int j = bl[fr]; j <= n; j++) {
            bucket[arr[j]]++;
            if (bucket[arr[j]] > bucket[md] || (bucket[arr[j]] == bucket[md] && arr[j] < md))
                md = arr[j];
            p[fr][bel[j]] = md;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        lsh[++cnt] = arr[i];
    }
    sort(lsh + 1, lsh + cnt + 1);
    cnt = unique(lsh + 1, lsh + cnt + 1) - (lsh + 1);
    for (int i = 1; i <= n; i++) {
        arr[i] = find(arr[i]);
    }
    block_init();
    init();
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        cout << lsh[query(l, r)] << '\n';
    }
}

关于莫队

莫队其实是一种离线的分块，它的优点在于省略了多余的操作，在原有查询基础上进行位移。这个后面再说