我的算法书 - 分块思想

一句话算法

分块把数组切成大约 $\sqrt n$ 个小段，整块用标记快速处理，零散边界直接暴力扫。

问题模型

以 LOJ 6280 数列分块入门 4 为例：

给定长度为 $n$ 的数组。
操作 0 l r c：把区间 [l,r] 中每个数加上 c。
操作 1 l r c：查询区间 [l,r] 的和对 c+1 取模。

如果每次都暴力扫 [l,r]，最坏是 $O(n)$ 。分块的目标是把一次操作拆成：

两侧不完整块：暴力处理。
中间完整块：用块级信息快速处理。

核心直觉

分块不是一棵树，而是“暴力 + 批处理”的折中。

把数组按块长 B 切开：

[1 ... B] [B+1 ... 2B] [2B+1 ... 3B] ...

一次区间操作最多碰到两个不完整块。它们长度都不超过 B，暴力扫可以接受。中间完整块数量大约是 n / B，可以用懒标记和块和一次处理一个块。

所以一次操作复杂度大约是：

B+\frac{n}{B}

当 $B=\sqrt n$ 时，两部分平衡，复杂度约为 $O(\sqrt n)$ 。

维护信息

这个模板维护三类信息：

a[i]：位置 i 的基础值，不包含所在块尚未下放的 lazy_add。
lazy_add[b]：整块 b 被整体加上的懒标记。
block_sum[b]：块 b 的真实元素和，已经包含懒标记贡献。

为什么 block_sum 要包含懒标记贡献？因为查询完整块时可以直接加 block_sum[b]，不用再乘长度。

算法步骤

区间加

如果 l 和 r 在同一块，直接扫 [l,r]，更新 a[i] 和 block_sum。
否则：
- 暴力处理左侧零散部分。
- 对中间完整块更新 lazy_add 和 block_sum。
- 暴力处理右侧零散部分。

区间求和取模

如果 l 和 r 在同一块，逐个加 a[i] + lazy_add[belong[i]]。
否则：
- 左右零散块逐个加真实值。
- 中间完整块直接加 block_sum[b]。
每一步都对模数取模，避免数值过大。

算法证明

关键不变量： 对任意位置 i，它的真实值等于 a[i] + lazy_add[belong[i]]；对任意块 b，block_sum[b] 等于该块所有真实值之和。

初始化： lazy_add 全为 0，block_sum 由原数组求和，不变量成立。
零散修改： 直接修改 a[i]，并同步给所在块的 block_sum 加上变化量。真实值和块和都正确。
整块修改： 不逐个改 a[i]，只给 lazy_add[b] 加 v，同时给 block_sum[b] 加 块长 * v。块内每个真实值都增加 v，块和也同步增加。
查询： 零散部分按真实值 a[i]+lazy_add 累加，完整块直接用 block_sum，正好覆盖 [l,r] 且不重不漏。

复杂度分析

设块长为 $B$ 。

预处理复杂度： $O(n)$ 。
单次操作复杂度： $O(B+n/B)$ 。
取 $B \approx \sqrt n$ 时，单次操作复杂度为 $O(\sqrt n)$ 。
空间复杂度： $O(n)$ 。

“均值不等式的理解”

对 $B+\frac nB$ 来说，当两个部分数量级接近时最小，所以令 $B \approx \sqrt n$ 。这就是分块常用根号块长的原因。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

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

using i64 = long long;

struct SqrtDecomposition {
    int n = 0;
    int block_size = 1;
    int block_count = 0;
    vector<i64> a, block_sum, lazy_add;
    vector<int> belong, left_bound, right_bound;

    explicit SqrtDecomposition(const vector<i64>& init) {
        n = (int)init.size() - 1;
        block_size = max(1, (int)sqrt(n));
        block_count = (n + block_size - 1) / block_size;

        a = init;
        block_sum.assign(block_count + 1, 0);
        lazy_add.assign(block_count + 1, 0);
        belong.assign(n + 1, 0);
        left_bound.assign(block_count + 1, 0);
        right_bound.assign(block_count + 1, 0);

        for (int b = 1; b <= block_count; ++b) {
            left_bound[b] = (b - 1) * block_size + 1;
            right_bound[b] = min(n, b * block_size);
            for (int i = left_bound[b]; i <= right_bound[b]; ++i) {
                belong[i] = b;
                block_sum[b] += a[i];
            }
        }
    }

    void add(int l, int r, i64 v) {
        int lb = belong[l];
        int rb = belong[r];

        if (lb == rb) {
            for (int i = l; i <= r; ++i) {
                a[i] += v;
                block_sum[lb] += v;
            }
            return;
        }

        for (int i = l; i <= right_bound[lb]; ++i) {
            a[i] += v;
            block_sum[lb] += v;
        }

        for (int b = lb + 1; b <= rb - 1; ++b) {
            lazy_add[b] += v;
            block_sum[b] += 1LL * (right_bound[b] - left_bound[b] + 1) * v;
        }

        for (int i = left_bound[rb]; i <= r; ++i) {
            a[i] += v;
            block_sum[rb] += v;
        }
    }

    i64 query_mod(int l, int r, i64 mod) const {
        int lb = belong[l];
        int rb = belong[r];
        i64 ans = 0;

        auto add_mod = [&](i64 x) {
            ans = (ans + x) % mod;
        };

        if (lb == rb) {
            for (int i = l; i <= r; ++i) add_mod(a[i] + lazy_add[lb]);
            return ans;
        }

        for (int i = l; i <= right_bound[lb]; ++i) {
            add_mod(a[i] + lazy_add[lb]);
        }

        for (int b = lb + 1; b <= rb - 1; ++b) {
            add_mod(block_sum[b]);
        }

        for (int i = left_bound[rb]; i <= r; ++i) {
            add_mod(a[i] + lazy_add[rb]);
        }

        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    SqrtDecomposition ds(a);

    for (int i = 1; i <= n; ++i) {
        int op, l, r;
        i64 c;
        cin >> op >> l >> r >> c;

        if (op == 0) {
            ds.add(l, r, c);
        } else {
            cout << ds.query_mod(l, r, c + 1) << '\n';
        }
    }

    return 0;
}

测试用例

输入：

输出：

第三次操作后数组变成 [1,12,13,14,5]，总和为 45。查询 [2,4] 的和是 39，对 8 取模得到 7，但注意上面的第四条查询输入是 c=7，取模数为 8，输出应为 7。

应用分类详解

分块的本质是把“全局难维护”拆成“整块快处理 + 边界暴力”。

一、区间修改与区间查询

典型模式： 区间加、区间求和、区间最值等操作。 识别信号： 线段树能做但实现较长，或者数据范围允许 $O(\sqrt n)$ 。 核心建模： 完整块维护聚合信息，零散位置暴力处理。

应用场景	经典题目	核心思路
区间加区间和	LOJ 6280	整块打加法标记，块和同步更新
区间加单点查	LOJ 6277	整块懒标记，单点查询加上块标记

二、块内有序结构

典型模式： 区间查询小于某值的个数、前驱后继、众数近似等。 识别信号： 每块内部可以排序或维护辅助结构，但整体合并很麻烦。 核心建模： 修改时重建受影响块，查询时完整块二分。

应用场景	经典题目	核心思路
区间计数	LOJ 6281	每块维护排序数组，完整块二分统计

三、根号分治

典型模式： 操作参数有大小之分，小参数和大参数用不同策略。 识别信号： 复杂度形如 $x+\frac nx$ ，存在明显阈值。 核心建模： 小规模预处理，大规模暴力或反过来。

应用场景	经典题目	核心思路
跳跃类查询	luogu-P3203	块内预处理跳出当前块的位置

经典例题

LOJ 6280 数列分块入门 4 本文模板题。重点练习块和与整块加法标记的同步维护。
LOJ 6277 数列分块入门 1 区间加、单点查询。比本文模型更简单，适合作为第一道分块题。
luogu-P3203 弹飞绵羊。不是区间加模型，但非常适合理解“块内预处理 + 跨块跳转”的分块思想。

参考

https://oi-wiki.org/ds/decompose/