Update：2026.01.09 byx

---

树状数组是基于二进制划分与倍增的思想，线段树基于分治的思想。之所以能够高效修改和查询，就是把序列分成了大大小小的“段”，花费额外（增加空间，空间换时间）的代价对这些“段”管理的信息进行记录和更新，查询一个区间的信息，可以将这个区间分成几个已有的“段”结合，从而提高效率。

树状数组和线段树也有缺点，当需要维护一些不满足区间可加性、可减性信息时显得吃力，代码也不直观，需要深入理解并注意很多细节。

当维护的信息不满足区间合并性，例如区间众数，要提高效率，就需要对序列进行分块，分块的基本思想就是“大段维护，局部暴力”，预处理一些信息并保存起来，用空间换时间，分块更加通用、容易实现。

分块优点：思维简单，代码容易实现。能维护“不符合区间可并性”的信息，理论上能解决线段树所有问题，优美的暴力。

分块缺点：时间复杂度太大，$m$ 次操作达到 $O(m\sqrt{n})$ , $m$ 和 $n$ 能达到 $10^5$ , $10^6$ 会超时，线段树能解决 $10^6$ 规模的问题。

分块经典例题：

LOJ 分块入门有 9 个模板题，之后又被搬到 luogu 上，数据也加强了。

例1. P13976 数列分块入门 1

【题意简化】：给出一个长为 $n(1 \le n\le 3 \times 10^5)$ 的数列，以及 $n$ 个操作，操作涉及区间加法，单点查值。

【分析】：可以利用树状数组和线段树在 $O(N\log{N})$ 的时间解决，现在我们使用分块解决本问题。

首先我们设块长为 $L$，那么块的个数就是 $t=\left \lceil n/L \right \rceil \approx n/L$ 。对于任意一个区间 $(l,r)$，区间内整段只需要对其 $lazy$ 标记数组修改，对于开头、结尾不足整段的部分进行朴素修改，单次区间修改复杂度可以表示为 $O(L+t)$，那么根据不等式的性质:

$$L+t=L+n/L \ge 2 \times \sqrt{L*(n/L)}=2\sqrt{n}$$

当 $L=n/L$ 时，不等式等号成立，即 $L=\sqrt{n}$ 。

$n$ 次修改复杂度为 $O(n\sqrt{n})$, 单点询问复杂度 $O(1)$.

参考代码：点击

例2. P13977 数列分块入门 2

【题意简化】：给出一个长为 $n(1 \le n\le 2 \times 10^5)$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的元素个数。

【分析】：询问区间内小于 $x$ 的个数，如果不带修改，可以利用主席树解决，带上修改后，主席树维护起来也很困难，考虑使用分块。

分块后，可以将块内元素排序（不破坏原序列，使用辅助数组 或 vector），当询问时，整块内可以二分查找快速解决，开头和结尾部分朴素查询，那么单次询问复杂度就是 $O(L+t*\log{L})$ .

区间修改，对于整块，直接修改 $lazy$ 标记，开头和结尾部分朴素修改，然后重构辅助数组。

参考代码：点击

例3. P13978 数列分块入门 3

【题意简化】给出一个长为 $n(\le 2\times 10^5)$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内某个值 $x$ 的前驱（比其小的最大元素）。

【分析】动态维护区间内某个数的前驱。

利用辅助数组，块内排序，然后二分查找所有块内 $x$ 的前驱，对于前后两个零头部分直接暴力找到比 $x$ 小的最大数。

例4. P13979 数列分块入门 4

【题意简化】给出一个长为 $n(\le 3\times 10^5)$ 的数列，以及 $n$ 个操作，操作涉及区间加法，区间求和。

【分析】类似于 线段树2 ，如果用分块，可以维护两个 lazy ,一个代表区间所有数乘法标记，一个代表加法标记。注意在做区间乘法修改时，需要将原来块加标记同时扩大对应倍数。

例5. P13980 数列分块入门 5

【题意简化】给出一个长为 $n(3\times 10^5)$ 的数列 $a_1​\dots a_n(\le 2^{31}-1)$ ，以及 $n$ 个操作，操作涉及区间开方，区间求和。

【分析】类似于 P4145上帝造题的七分钟2 ，开方运算无法整体进行，只能逐一进行，但是直接暴力开方，时间复杂度无法接受。发现任意一个数开方 $6$ 次左右肯定为 $1$ ，之后开方不变，那么一个区间经过几次开方都会变为 $1$ 。那么分块后，利用标记表示块内最大数，最大数小于等于 $1$ 说明块内不需要逐一开方，区间修改时可以直接跳过本块。

例6. P13981 数列分块入门 6

【题意简化】给出一个长为 $n(n\le 3\times 10^5)$ 的数列，以及 $n$ 个操作，操作涉及单点插入，单点询问。

【分析】块状链表，块长 $\sqrt{n}$ , 每个块内创建一个 vector 。插入时，从头找到对应块位置，vector 直接插入，当块长超过 $2\sqrt{n}$ ，将本块拆分成两个块。单次插入时间复杂度为 $O(\sqrt{n})$，查询时间复杂度 $O(\sqrt{n})$ , 总时间复杂度为 $O(m\sqrt{n})$,$m$ 为操作总次数.

参考代码：点击

例7. P13982 数列分块入门 7

【题意简化】给出一个长为 $n(3 \times 10^5)$ 的数列，以及 $n$ 个操作，操作涉及区间乘法，区间加法，单点询问。

【分析】两个块标记，乘标记和加标记。

例8. P13982 数列分块入门 8

【题意简化】给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$。

【分析】利用 lazy 标记区间整体修改

例9. P13984 数列分块入门 9

【题意简化】给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及询问区间的最小众数。

【分析】静态区间众数问题，可以使用分块、莫队求解。类似问题P4168 蒲公英 要求强制在线，莫队就不行了。

区间众数不符合区间合并性，无法使用树状数组、线段树维护，可以使用分块。提前预处理好两个重要数组，z[i][j] 第 i 块到第 j 块的区间众数 , pre[i][j] 表示前 $i$ 块 $j$ 出现的次数。

初始化 pre[i][j],z[i][j] 是关键 。pre[i][j] 可以由 pre[i-1][j] 累加上第 $i$ 块的贡献得到, z[i][j] 可以由 z[i][j-1] 众数，暴力检测 [st[j],ed[j]] 能否是区间众数。

提前预处理好，查询时，整段众数可以由 z[bl+1][br-1] , 暴力检测区间 [l,ed[bl]] 与 [st[br],r] 每一个数能否成为众数。

注意需要对原数组离散化，之后再还原为原值。

参考代码：点击

---

课后练习

利用分块解决 P3372 线段树 1

利用分块解决 P3369【模板】普通平衡树

---

分块其他例题应用，请点击 分块应用

---

学习完毕

{{ select(1) }}

• YES
• NO