分块指北

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

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

0 平衡思想

我们需要做的,就是通过设计一个平衡方案,使得我们可以分而在最小的复杂度内解决所有的操作。

大致有两种应用:

  1. 处理出信息簇,将询问分摊在这些簇上,使得维护簇的复杂度和簇内朴素算法的复杂度平衡。常用在维护图类型信息上,即给定信息点集以及之间的关系边集,每次给定一个子集进行操作。经典例子是序列问题的分块解法。
  2. 发现信息的特殊性质,将信息分为多个部分,并用不同的方式处理,达到总体的平衡。此类平衡常被称作根号分治。

1 分块

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)\) 的。

值域分块作为二次平衡的体现,会经常在经过平衡后的算法中出现。例子有作业risrqnis

1.3 操作分块

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

顾名思义,操作分块就是对操作序列进行分块。我们可以将操作块看作一个信息簇,在处理完该块后统一重构。当处理到一块时,我们已经将操作分成了两个部分:第一个部分是先前块内的修改,这些部分已经在实际的信息点上进行完了,因此这部分是静态的贡献。第二个部分是当前块内的修改,而这些修改总数不会达到块大小,因此可以朴素地计算这部分的贡献。
计算后将这两部分贡献结合即可得到对应询问的答案。

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

1.4 树分块

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

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

例子有王室联邦第七分块等这场战争结束之后

1.5 块状链表

又称“五分钟写完的平衡树”

具体地,我们对序列分块,每块内部使用类链表方式存储,所有块链首也使用类链表方式存储。这样我们就得到了一个两层的链表。

为什么要这么做呢?众所周知,链表的直接插入删除速度很快,但是其复杂度瓶颈在于 \(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)\),不会劣化。

例子是文本编辑器带插入区间 K 小值

1.6 二维分块

这里 \(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)\)

例题:rdiq博丽灵梦
关于 \(O(1)-O(\sqrt n)\) 的做法可以看rvrewsus

根号分治

展开说一下。

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

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

类似的内容用在图上也可以,我们可以将度数超过 \(\sqrt m\) 的点和其余点分离,以类似的思想进行处理。这又被称作度数分块。例题有Graph

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

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

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

莫队

详见这篇博客

奇妙分块

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

1. 分块并按块离线,执行高复杂度算法

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

例题:[Ynoi2013] D2T2
加入根号分治和散块特殊处理的例题:rvrewsus

2. 预处理跳块

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

例题:弹飞绵羊
加入一些均摊分析的例题:rfplca

trick 的合并(例题集合)

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

    原文作者:joke3579
    原文地址: https://www.cnblogs.com/joke3579/p/sqrt_tech.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞