我的算法书 - 分块思想

一句话算法

分块把数组切成大约 $\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$ 。这就是分块常用根号块长的原因。

代码实现

C++

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
119
120

        #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) {
            // C++ 的 % 在负被除数时返回负余数，而「取模」的数学含义要求结果落在 [0, mod)；
            // 原写法在数组含负数时会输出负值（例如 mod = 5 时给出 -3 而不是 2）。
            ans = ((ans + x) % mod + mod) % 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;
}

Python

取模是数学模（结果落在 $[0, mod)$ ）：原 C++ 用 % 对负数返回负余数，已修复为 ((ans + x) % mod + mod) % mod。

python

        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

        # 分块（SqrtDecomposition）：区间加、区间和取模查询。
# 与 C++ 版一致：构造时传入 1 下标数组 init（init[0] 不用，长度 n+1），
# 内部自动按 sqrt(n) 分块；add 是区间加，query_mod 是区间和再取模。
# 注意 C++ 版语义：query_mod(l, r, mod) 里传入的 mod 已经是 c+1
# （见源文件 main），调用方需保持同一约定。
# 调用示例：ds = SqrtDecomposition([0, 3, 1, 4]); ds.add(1, 2, 5); ds.query_mod(2, 3, 7)
# Python 的 int 是任意精度，C++ 的 i64 / 1LL 防溢出写法在这里无需担心。
# block_count 可为 0（n = 0 时），此时 add/query_mod 不应被调用（区间为空）。

import math

type Seq = list[int]  # 长度 n+1 或 block_count+1 的 int 序列


class SqrtDecomposition:
    """分块：block_size 为块长，block_count 为块数，1 <= 块编号 <= block_count。"""

    n: int
    block_size: int
    block_count: int
    a: Seq
    block_sum: Seq
    lazy_add: Seq
    belong: Seq
    left_bound: Seq
    right_bound: Seq

    def __init__(self, init: Seq) -> None:
        self.n = len(init) - 1  # C++ 同样按"传入数组长度 - 1"取 n
        self.block_size = max(1, math.isqrt(self.n))  # max(1, ...) 防 n=0 时块长为 0
        self.block_count = (self.n + self.block_size - 1) // self.block_size  # 上取整

        self.a = list(init)  # 复制一份，避免与调用方的数组共享引用
        self.block_sum = [0] * (self.block_count + 1)
        self.lazy_add = [0] * (self.block_count + 1)
        self.belong = [0] * (self.n + 1)
        self.left_bound = [0] * (self.block_count + 1)
        self.right_bound = [0] * (self.block_count + 1)

        for b in range(1, self.block_count + 1):
            self.left_bound[b] = (b - 1) * self.block_size + 1
            self.right_bound[b] = min(self.n, b * self.block_size)
            for i in range(self.left_bound[b], self.right_bound[b] + 1):
                self.belong[i] = b
                self.block_sum[b] += self.a[i]

    def add(self, l: int, r: int, v: int) -> None:
        """区间修改：a[l..r] 整体加 v。

        中间整块只更新 lazy_add 和 block_sum（不逐点落到 a 上），
        散块才逐点加并同步块和——这是分块的核心不变量。
        """
        lb = self.belong[l]
        rb = self.belong[r]

        if lb == rb:
            for i in range(l, r + 1):
                self.a[i] += v
                self.block_sum[lb] += v
            return

        for i in range(l, self.right_bound[lb] + 1):
            self.a[i] += v
            self.block_sum[lb] += v

        for b in range(lb + 1, rb):
            self.lazy_add[b] += v
            self.block_sum[b] += (self.right_bound[b] - self.left_bound[b] + 1) * v

        for i in range(self.left_bound[rb], r + 1):
            self.a[i] += v
            self.block_sum[rb] += v

    def query_mod(self, l: int, r: int, mod: int) -> int:
        """区间查询：a[l..r] 的和，边累加边取模。

        C++ 用 lambda add_mod 逐步取模防溢出；Python int 任意精度，
        但保留逐步取模写法以保持语义一致（结果相同）。
        """
        lb = self.belong[l]
        rb = self.belong[r]
        ans = 0

        if lb == rb:
            for i in range(l, r + 1):
                ans = (ans + self.a[i] + self.lazy_add[lb]) % mod
            return ans

        for i in range(l, self.right_bound[lb] + 1):
            ans = (ans + self.a[i] + self.lazy_add[lb]) % mod

        for b in range(lb + 1, rb):
            ans = (ans + self.block_sum[b]) % mod

        for i in range(self.left_bound[rb], r + 1):
            ans = (ans + self.a[i] + self.lazy_add[rb]) % mod

        return ans

测试用例

输入：

输出：

第三次操作后数组变成 [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/