分块指北

分块思想最根本的部分是”平衡”二字。
以下例题大致按难度排序,但可能有并列

当前版本是大纲,关于题目的分析很可能并不完善。
以及介绍部分可能也不全面/完善,如有疏漏敬请各位读者指正!

*[En]*

**

大致有两种应用:

1.1 序列分块

分块最基础的表示就是利用时间复杂度的平衡维护序列上的信息。我们通过对序列的适当的划分平衡复杂度。正常而言,我们将整个序列划分为长度为 (B) 的块,最后长度小于 (B) 的自成一块。

复杂度的平衡通过块信息的合并完成。
不难发现,对区间的操作可以被拆分为对一系列整块的操作和对 (O(1)) 个散块的操作。因此我们对散块实行复杂度大的暴力算法,对整块采用复杂度小的整体标记,即可做到平衡修改的复杂度。同理,我们将整块的信息合并,在需要时直接加入整块信息,而对散块可以直接扫描每个元素。
这就做到了复杂度平衡。

在这部分中,分块常用于替代线段树,维护一些无法采用线段树维护的信息。有时需要处理任意两块间的信息,容易发现这样的信息数是 (O(n)) 的。
这类问题的例子是最初分块第二分块

1.2 值域分块

一般来说,值域分块会作为一个辅助工具出现在题目当中。

值域分块是权值线段树的替代,其大多数应用同样是平衡复杂度:假设我们需要进行 (O(n\sqrt n)) 次插入元素,但是只需要 (O(n)) 次查询,那采用权值线段树就不能做到整体的平衡了。我们需要 (O(1)) 插入 (O(\sqrt n)) 查询的数据结构。这就自然想到值域分块。

以值域分块维护集合第 (k) 小为例:每个块上记录块内总元素数,每个值的位置记录该值出现了多少次。插入只需要维护当前位置和所在块的信息,因此是 (O(1)) 的。查询时,首先扫描所有块,找到第 (k) 小值所在的块,再扫描对应块找到真正的第 (k) 小值,因此是 (O(\sqrt n)) 的。

1.3 操作分块

常常出现在”不带修改很可做,但带了修就都没法维护了,而且只有修改的话不难维护”的题上。

*[En]*

**

计算后将这两部分贡献结合即可得到对应询问的答案。

操作分块适用于整体重构复杂度小的信息,经典例子是单点修改和虚树。值得注意的是,操作分块的性质使得它可能出现于优化不可带修信息的求解上。这样的例子有CF925E第十分块

1.4 树分块

这里的树分块并不是树上莫队相关的内容。这里涉及的树分块是将树分成 (B) 个边集不交的极大子树,每个联通块以关键点(通常选联通块的 LCA)作为信息簇的存储位置。

有两种树分块的形式。
第一种是简易树分块。我们直接随机 (B) 个关键点,如果树根不在其中的话加入树根。对于每个点,将其与其最深的关键祖先放在同一个联通块内。这样做的常数较大,而且有小概率复杂度爆炸。mrsrz 在一篇题解中提及了一种确定性的算法,能使得每个点到关键点的距离不超过 (B),并且总数不超过 (\frac nB)。具体地,我们每次选择一个深度最大的非关键点,然后若它的 (1\sim S) 级祖先都不是关键点,则我们把它的 (S) 级祖先标记为关键点。由标记过程可知距离不超过 (S),并且每标记一个关键点,至少有 (S) 个点不会被标记,所以关键点数量也是正确的。
第二种是 top cluster 划分。具体看 zx2003 的 2021 集训队论文,先咕着。

1.5 块状链表

*[En]*

**

为什么要这么做呢?众所周知,链表的直接插入删除速度很快,但是其复杂度瓶颈在于 (O(n)) 的定位元素。回顾值域分块查询 (k) 小的方式。我们发现,将此方式套用在块状链表结构上,我们就能以 (O(\sqrt n)) 的复杂度定位到一个确定元素。这样我们就得到了 (O(\sqrt n)) 复杂度进行修改和查询的链表。
普通链表不需要在意在同一个位置插入多次的情况,但是块状链表需要考虑这个问题。众所周知,块大小的平均是分块算法保证复杂度(和常数)的根本。正常的分块是静态的,在初始化后不需要刻意地维护块大小。然而块大小在块状链表中是可变的,因此维护块大小 (=O(\sqrt n)) 就变得必要起来。我们需要在块大小大于 (2\sqrt n) 时分裂块,相邻两块加和 (\le \sqrt n) 时合并块(一般而言不用合并的复杂度正确)。需要使用块大小渐进相关的维护方法,因此如果维护值域信息的话需要斟酌,或是采用只需要保存整块信息的值域分块。
采取以上做法即可将单次操作的复杂度控制在 (O(\sqrt n)) 内。

一个 trick 是内层链表采用 vector 实现,这样内层的常数会很小。而且插入复杂度也是 (O(\sqrt n)),不会劣化。

这里 (n) 的范围仍然是 (10^5) 的,信息点集大小 (=O(n))。我们需要维护 (n\times n) 的平面。

一维分块的散块可以随便做,但是二维分块的情况就不是那么简单了。这里的散块很有可能退化成 (O(n)) 甚至更劣的大小。而且直接套用 (\sqrt n \times \sqrt n) 的块长会导致空间急速增加。
这里讨论的信息是满足结合律、合并快的信息,因此每个块维护的信息大小默认是 (O(1))。

容易发现一层分块无论如何都会产生散块范围过大的问题。因此考虑分二级块。我们首先将平面分成 (\sqrt n) 个 (n^{0.75}\times n^{0.75}) 的一级块,随后将每个一级块分成 (\sqrt n) 个 (n^{0.5}\times n^{0.5}) 的二级块。一级块维护一级块的二维前缀和,二级块维护所在一级块内二级块的二维前缀和。这部分的空间复杂度是 (O(n)) 的。这样(部分地)解决了整块和右上角散块的问题。
然后考虑右端和上端的散块。以上端为例。我们将平面横着分为 (n\times n^{0.75}) 的一级块,块内分 (\sqrt n) 个 (n^{0.75}\times n^{0.5}) 的块。竖着同理。每个块维护所在区域内块的二维前缀和。
这样加入点是 (O(\sqrt n)) 的。查询二维前缀和整块是 (O(1)) 的。

随后我们即可发现,每次查询都会剩余矩形边上的一圈范围,这些范围的宽度是 (< n^{0.5}) 的。这部分只能根据维护的信息调整。以区间本质不同逆序对为例。应用莫队后能发现这是二维数点问题,且横纵坐标彼此不同。我们对纵坐标分 (\sqrt n) 块,容易发现每种散块都只会被分到一个块内,且它们都对应着一个前缀。加入信息点时,更新所在块内对应可能有贡献的散块。能发现每个信息点对应能贡献的散块只有 (O(n)) 个,因为满足条件的散块都应该覆盖该点且未覆盖该点所在 (n^{0.5}\times n^{0.5}) 块右上角位置。因此总时间复杂度为 (O(n\sqrt n)) 个。
由于每个散块信息都已经在加入时更新完,这就做到了散块 (O(1)) 查询。

因此有 (O(\sqrt n) – O(1))。

展开说一下。

这一类问题的标准 Trick 是分类讨论贡献次数大于/小于 (\sqrt n) 的对象,并对这两个部分根据不同的性质采用不同的方式求出贡献。或者形式化地,我们需要维护序列 (s) 的值域相关信息,而序列 (s) 满足 (\sum s_i = n)。

对于众数而言是出现次数大于 (\sqrt n) 的元素不会超过 (\sqrt n) 个,因此可以对每个出现次数大于 (\sqrt n) 的元素以 (O(n)) 的方式求出贡献;反之则有元素出现次数小于 (\sqrt n),可以根据出现次数统计答案。例子是众数

另一种我不知道有没有其他很有趣的应用。具体而言,可以通过一定处理将各操作划分为不交的贡献集,分别对这些贡献集进行处理。这类操作在特定情况下又被称作按块离线,使用到这个 trick 的题有第六分块。另一个例子是 risrqnis,这道题包含好几个 Trick,是很好的分块入门例题。Solution

在这里也提一下贡献计算的问题。在根号分治题目中,常常出现不同分类的元素互相贡献的情况,这点需要根据不同的性质与具体情况具体分析。例子有第十三分块,这里的链接指向 NOI2020 D1T3。

启发式思想同样可以自然地与根号分治相关题目结合,这常用于修改时需要将贡献合并的情况。我们仍然可以根据贡献次数分类讨论涉及不同部分的修改。具体例子有第四分块。注意这里和第二分块的 trick 并不同质。

其实这部分是因为 ynoi 的题十分奇怪没法好好分类所以单拎出来提一下。

假设我们有一个对 (n) 长度序列执行的复杂度为 (O(n^2)) 的算法,并且这个算法处理的信息支持 (O(1)) 合并(例如最大值、加和等)。我们将序列分块,块长为 (\sqrt n)。对每一块分别执行此算法,单块复杂度为 (O(n))。总时间复杂度为 (O(n\sqrt n))。
按块进行可以降低空间复杂度。

有一种树上信息,需要每次跳父亲得到。我们将树改成 dfn 序,然后就变成从一个下标跳到另一个下标。同时维护的信息需要满足结合律,合并也需要快一些,最好 (O(1))。我们首先分块,预处理出每个点在块内跳跃的全信息,以及其跳出块的位置。这样每个块就可以经过一次信息合并处理完了。
适用于任意有 (n-1) 条关系边的结构。

stdmxeypz:根号分治 + 平衡思想。
初始化:根号分治,(\le \sqrt n) 部分的处理很独特。
盼君勿忘:根号分治做到 (O(\sqrt n)) 维护确定信息点集下的单次查询。信息点集采用莫队计算。

Original: https://www.cnblogs.com/joke3579/p/sqrt_tech.html
Author: joke3579
Title: 分块指北

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/222815/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总