分块思想
简介
其实，分块是一种思想，而不是一种数据结构．
从 NOIP 到 NOI 到 IOI，各种难度的分块思想都有出现．
分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度．
分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度．
分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息．
当然，分块的缺点是渐近意义的复杂度，相较于线段树和树状数组不够好．
不过在大多数问题上，分块仍然是解决这些问题的一个不错选择．
下面是几个例子．
区间和
给定一个长度为 𝑛n
的序列 {𝑎𝑖}{ai}，需要执行 𝑛n 次操作．操作分为两种：
- 给 𝑎𝑙 ∼𝑎𝑟al∼ar 之间的所有数加上 𝑥x；
- 求 ∑𝑟𝑖=𝑙𝑎𝑖∑i=lrai．
1 ≤𝑛 ≤5 ×1041≤n≤5×104
我们将序列按每 𝑠s 个元素一块进行分块，并记录每块的区间和 𝑏𝑖bi．
𝑎1,𝑎2,…,𝑎𝑠⏟⏟⏟𝑏1,𝑎𝑠+1,…,𝑎2𝑠⏟⏟⏟𝑏2,…,𝑎(𝑠−1)×𝑠+1,…,𝑎𝑛⏟_⏟_⏟𝑏𝑛𝑠a1,a2,…,as⏟b1,as+1,…,a2s⏟b2,…,a(s−1)×s+1,…,an⏟bns
最后一个块可能是不完整的（因为 𝑛n 很可能不是 𝑠s 的倍数），但是这对于我们的讨论来说并没有太大影响．
首先看查询操作：
- 若 𝑙l 和 𝑟r 在同一个块内，直接暴力求和即可，因为块长为 𝑠s，因此最坏复杂度为 𝑂(𝑠)O(s)．
- 若 𝑙l 和 𝑟r 不在同一个块内，则答案由三部分组成：以 𝑙l 开头的不完整块，中间几个完整块，以 𝑟r 结尾的不完整块．对于不完整的块，仍然采用上面暴力计算的方法，对于完整块，则直接利用已经求出的 𝑏𝑖bi 求和即可．这种情况下，最坏复杂度为 𝑂(𝑛𝑠 +𝑠)O(ns+s)．
接下来是修改操作：
- 若 𝑙l 和 𝑟r 在同一个块内，直接暴力修改即可，因为块长为 𝑠s，因此最坏复杂度为 𝑂(𝑠)O(s)．
- 若 𝑙l 和 𝑟r 不在同一个块内，则需要修改三部分：以 𝑙l 开头的不完整块，中间几个完整块，以 𝑟r 结尾的不完整块．对于不完整的块，仍然是暴力修改每个元素的值（别忘了更新区间和 𝑏𝑖bi），对于完整块，则直接修改 𝑏𝑖bi 即可．这种情况下，最坏复杂度和仍然为 𝑂(𝑛𝑠 +𝑠)O(ns+s)．
利用均值不等式可知，当 𝑛𝑠 =𝑠ns=s，即 𝑠 =√𝑛s=n 时，单次操作的时间复杂度最优，为 𝑂(√𝑛)O(n)．
参考代码
---|---
## 区间和 2
上一个做法的复杂度是 Ω(1),𝑂(√𝑛)Ω(1),O(n)．
我们在这里介绍一种 𝑂(√𝑛) −𝑂(1)O(n)−O(1) 的算法．
为了 𝑂(1)O(1) 询问，我们可以维护各种前缀和．
然而在有修改的情况下，不方便维护，只能维护单个块内的前缀和．
以及整块作为一个单位的前缀和．
每次修改 𝑂(𝑇 +𝑛𝑇)O(T+nT)．
询问：涉及三部分，每部分都可以直接通过前缀和得到，时间复杂度 𝑂(1)O(1)．
## 对询问分块
同样的问题，现在序列长度为 𝑛n，有 𝑚m 个操作．
如果操作数量比较少，我们可以把操作记下来，在询问的时候加上这些操作的影响．
假设最多记录 𝑇T 个操作，则修改 𝑂(1)O(1)，询问 𝑂(𝑇)O(T)．
𝑇T 个操作之后，重新计算前缀和，𝑂(𝑛)O(n)．
总复杂度：𝑂(𝑚𝑇 +𝑛𝑚𝑇)O(mT+nmT)．
𝑇 =√𝑛T=n 时，总复杂度 𝑂(𝑚√𝑛)O(mn)．
### 其他问题
分块思想也可以应用于其他整数相关问题：寻找零元素的数量、寻找第一个非零元素、计算满足某个性质的元素个数等等．
还有一些问题可以通过分块来解决，例如维护一组允许添加或删除数字的集合，检查一个数是否属于这个集合，以及查找第 𝑘k 大的数．要解决这个问题，必须将数字按递增顺序存储，并分割成多个块，每个块中包含 √𝑛n 个数字．每次添加或删除一个数字时，必须通过在相邻块的边界移动数字来重新分块．
一种很有名的离线算法 [莫队算法](../../misc/mo-algo/)，也是基于分块思想实现的．
## 练习题
* [UVa - 12003 - Array Transformer](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3154)
* [UVa - 11990 Dynamic Inversion](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3141)
* [SPOJ - Give Away](http://www.spoj.com/problems/GIVEAWAY/)
* [Codeforces - Till I Collapse](http://codeforces.com/contest/786/problem/C)
* [Codeforces - Destiny](http://codeforces.com/contest/840/problem/D)
* [Codeforces - Holes](http://codeforces.com/contest/13/problem/E)
* [Codeforces - XOR and Favorite Number](https://codeforces.com/problemset/problem/617/E)
* [Codeforces - Powerful array](http://codeforces.com/problemset/problem/86/D)
* [SPOJ - DQUERY](https://www.spoj.com/problems/DQUERY)
**本页面主要译自博文[Sqrt-декомпозиция](http://e-maxx.ru/algo/sqrt_decomposition) 与其英文翻译版 [Sqrt Decomposition](https://cp-algorithms.com/data_structures/sqrt_decomposition.html)．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．**
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/decompose.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/decompose.md "edit.link.title")
> __本页面贡献者：[Ir1d](https://github.com/Ir1d), [StudyingFather](https://github.com/StudyingFather), [Xeonacid](https://github.com/Xeonacid), [Yanjun-Zhao](https://github.com/Yanjun-Zhao), [c-forrest](https://github.com/c-forrest), [HeRaNO](https://github.com/HeRaNO), [Chrogeek](https://github.com/Chrogeek), [Enter-tainer](https://github.com/Enter-tainer), [gi-b716](https://github.com/gi-b716), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [linghaiyi](https://github.com/linghaiyi), [Tiphereth-A](https://github.com/Tiphereth-A), [yiyangit](https://github.com/yiyangit)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用