浅谈离线分治算法

前言

貌似这篇文章已经咕了快半年了(捂脸逃……

分治算法,即“分而治之”,每次将当前的问题化成两个或更多相同或相似的子问题,再对每个分出的问题进行同样的操作…… 直到子问题足够地小,让我们能够方便地直接求解。归并排序便是分治算法的经典应用之一。

不过,在过去我们遇到的题目中,我们往往是对题目中所询问的数据进行分治的。那么,在允许离线算法的题目中,我们可以运用类似思想对询问本身进行分治吗?

离线分治算法的主要思想就是把分治思想用在操作集上,而其在时间复杂度上的代价仅仅是多乘上一个 O(logn)\mathcal{O}(\log{n})。 本文将介绍两种离线分治算法:

  • 基于数值的离线分治算法;
  • 基于时间的离线分治算法。

前者往往就是整体二分;而后者即为 CDQ 分治。本文将从整体二分讲起,引出基于数值的离线分治算法的思想,再类比着介绍基于时间的离线分治算法。

本文极大程度上参考了许昊然所著《浅谈数据结构题的几个非经典解法》一文以及李煜东所著《算法竞赛进阶指南(第二版)》一书(强烈安利),在此对包含两位作者在内的所有我在整理本文过程中所有参考过的文章(完整列表见文末)的作者表示衷心感谢。

基于数值的离线分治

这一算法又有一个更加广为人知的名字:整体二分

大家对于二分算法大概是非常熟悉的,但是我们接触到的传统的二分往往是针对单个询问进行二分。而整体二分则更进一步,对多个同类操作(包括修改和查询)一起二分答案,同时依据当前二分的判定值对当前操作集进行分类,再应用分治思想分而治之。而这一算法的经典应用即为区间第 kk 小。我们不妨以其作为例子来介绍整体二分。

静态区间第 k 小

题面

对于一个长度为 NN 的数列,现有 QQ 次询问。每次询问给出 l,r,kl, r, k,试求数列中下标在 [l,r][l, r] 中第 kk 小的数的数值。

数据范围

1N1051 \le N \le 10^5

1Q5×1031 \le Q \le 5 \times 10^3

题目链接

分析与实现

主席树?当然可以,就是容易 MLE,或者更糟,写挂(逃…

如果是对于单次查询,我们显然是可以先对区间进行预处理然后进行二分的。一种显而易见的思路就是将数值离散化然后开一个数组来记录每一个值在区间内出现的次数然后对前缀和进行二分。但是,当我们面对多个询问的时候,如果对每一个询问都进行预处理然后再二分,这样的复杂度显然是无法接受的。

不难发现对于每个询问其实预处理的过程都是大致相同的。那么我们是否可以对多个询问同时进行二分操作呢?

假设题目给定了由 nn 个询问组成的一个询问集合 QQ,并且我们知道所有出现过的数值的区间为 [l,r][l, r]。二分过程中,我们记 mid=12(l+r)mid = \frac{1}{2}(l+r)。在每一层递归中,我们首先对于 QQ 内每一个询问,求得该询问区间中数值在 [l,mid][l, mid] 范围内的值的个数 cntcnt。接下来,我们以此将 QQ 中的询问分为两类:cntkcnt \ge k 的以及 cnt<kcnt < k 的。我们用 Q1Q _1Q2Q_2 来表示这两类询问。

对于 Q1Q_1 中的询问,我们显然可以在 [l,mid][l, mid] 这一范围中求得答案。换句话说,[l,r][l, r] 中的第 kk 小即 [l,mid][l, mid] 中的第 kk 小;而对于 Q2Q_2 中的询问,我们便可以得知答案坐落于 (mid,r](mid, r] 这一范围中。显然,求 [l,r][l, r] 中的第 kk 小等价于求 (mid,r](mid, r] 中的第 kcntk - cnt 小(我们需要剔除 [l,mid)[l, mid) 中的数)。通过这种方式,我们可以把问题 QQ 拆分成 Q1Q_1Q2Q_2 两个子问题然后对它们进行分治并递归求解。递归结束于 l=rl = r,记此时的询问集为 QQ’,则 QQ’ 中的所有询问的答案即为 rr,便可以求解问题了。

我们最后需要解决的问题便是如何求得 cntcnt 了。我们可以考虑将原始数列中的数值离散化,然后用一个树状数组来维护这一信息。树状数组的第 ii 位表示数列中第 ii 位上的值是否坐落于 [l,mid][l, mid] 范围内,因此我们只需要在树状数组上求[L,R][L, R] 区间的区间和便可以得知下标 [L,R][L, R] 间有多少个数坐落于 [l,mid][l, mid] 范围内,即 cntcnt

具体实现时,我们可以在记录数列中每个数的原始下标后对数列按数值从小到大排序。我们可以通过二分搜索快速查找到 ll 的位置,接下来我们便可以轻松地对于 [l,mid][l, mid] 中的每个值更新树状数组中的信息。再求得 cntcnt 后我们再逐一撤销我们方才对树状数组进行的更改以为接下来递归中求 cntcnt 做准备。需要注意的是,撤销更改时不可以直接用 memset,若是如此每一次预处理就与原数组长度有关而并非与当前二分区间有关了,而这会导致复杂度的变化(下面会给出详细说明)。显然,这一过程复杂度是 O(mlogn)\mathcal{O}(m\log{n}) 的,其中 mm 是当前二分区间的长度。总的复杂度是 O(nlog2n)\mathcal{O}(n\log^2{n}) 级别的(下面也会给出详细说明)。

完整参考代码

复杂度分析

至于复杂度,这里引用《浅谈数据结构题的几个非经典解法》一文中的相关证明:

定义 T(C,S)T(C, S) 表示当前待二分区间长度为 CC,待二分序列长度为 SS,且记对于长度为 mm 的序列单次处理复杂度为 O(f(m))\mathcal{O}(f(m)),则在 O(f(n))n\mathcal{O}(f(n)) \ge n 的前提下有:

T(C,S)=T(C2,S)+T(C2,SS)+O(f(S))T(C, S) = T(\frac{C}{2}, S’) + T(\frac{C}{2}, S - S’) + \mathcal{O}(f(S))

解得:

T(C,S)O(f(n)logn)T(C, S) \le \mathcal{O}(f(n)\log{n})

而如果每一次处理的复杂度都与序列长度 nn 有关,则有:

T(C,S)=T(C2,S)+T(C2,SS)+O(n)T(C, S) = T(\frac{C}{2}, S’) + T(\frac{C}{2}, S - S’) + \mathcal{O}(n)

解得:

T(C,S)=O(nS)T(C, S) = \mathcal{O}(nS)

不难发现,这样一来实际上复杂度就变得与暴力没什么区别了……

那么对于这一例题中我们的做法,我们先对数值进行排序,然后在二分查找过程中我们每次直接通过二分查找来确定端点位置,其复杂的是 O(mlogm)\mathcal{O(m\log{m})} 的,其中 mm 为当前处理区间长度。总的复杂度即 O((n+Q)lognlogC)\mathcal{O}((n + Q) \log{n}\log{C}),在该题数据范围下就是 O(nlog2n)\mathcal{O}(n\log^2{n}) 级别的。


由上面的例子,我们可以初步窥见整体二分适用的问题范围。首先,最显然而又最基本的是,询问的答案必须具有可二分性,并且题目允许离线算法。

其次,我们注意到在上例中二分时我们每一次预处理只与当前区间长度有关。这是因为其余部分对答案的贡献是固定的。具体地阐述,假设我们计算某询问区间内的第 kk 大时,假设该区间内数值的范围为 [L,R][L, R],当我们正在二分区间 [l,r][l, r] 时,[l,r][l, r] 以外的区间(即 [L,l)[L, l)(r,R](r, R])对答案的贡献是固定不变的(询问区间内数值在这些区间内的数的个数固定),因此我们没有必要去重复计算那两个区间对答案的贡献,直接加上即可。由此,贡献也应当是可加的,并且满足交换律和结合律。

那么,如果我们需要支持的操作不仅仅有询问,同时还要有修改呢?事实上,只要加入修改操作后我们依然能够做到二分时每一次预处理只与当前区间长度有关,我们就可以继续使用整体二分。

动态区间第 k 小

题面

对于一个长度为 NN 的数列,现有两类共 QQ 次操作:

  • 将第 ii 个数的值修改为 vv
  • 询问第 ll 个数和第 rr 个数之间第 kk 小的数值。

数据范围

1N5×1041 \le N \le 5 \times 10^4

1Q1041 \le Q \le 10^4

题目链接

分析与实现

本题与上一例唯一的区别便在于新加入了修改操作,这样一来上例中的询问集 QQ 在本题中就变成可以含有询问即修改两种操作的操作集了。我们不妨把每个修改操作拆成两步:先删除该位置上原值,再在该位置上插入新值。同时,序列的初始化也可看作 nn 次在位置 ii 插入新值。

我们注意到每一次修改操作其实对答案的贡献是独立的。具体地说,假设二分过程中当前某区间值域为 [L,R][L, R],当前二分区间为 [l,r][l, r]。我们若是将该区间内某位置上的值由 aia_i 改变为 ai (lair)a_i’ \ (l \le a_i’ \le r) ,并不会改变 [l,r][l, r] 以外的区间(即 [L,l)[L, l)(r,R](r, R] 这两个区间对答案的贡献。 由此,每一次预处理的复杂度依然仅仅是与当前二分区间有关的,可以使用整体二分。

故我们依然采用与上例类似的思路对所有操作进行二分。不同之处在于,由于修改这一操作的引入,我们不能随意改变操作的顺序。因此,区别仅仅在于求 cntcnt 这一过程的实现。我们不能再像之前一样先对值排序然后二分,因为那样会改变操作的顺序。对于 QQ 内的操作,我们必须按照原顺序进行遍历,查询和修改同时进行(若操作为修改,只应用值在 [l,mid][l, mid] 区间之内的)。另外在将 QQ 分类为 Q1Q_1Q2Q_2 时也要单独开两个单独的空间来进行分类以防止改变操作之间的顺序。

完整参考代码

小结

整体二分是一种应用于允许离线具有多组询问且具有二分性问题的一种算法,其思想即将多组操作一起二分从而减小复杂度。精炼地说,整体二分实际上就是二分+分治二分是对于答案值的二分,而分治则是对于操作集的分治,从而达到对多个同类询问一起进行二分求解的效果。这其中最关键的地方是,我们必须确保二分过程中每一次预处理的复杂度应与当前二分区间的长度区间有关,而绝对不能与整个序列长度有关。如果我们记预处理的复杂度为 O(f(n))\mathcal{O}(f(n)),则整体二分的复杂度为 O(f(n)logn)\mathcal{O}(f(n)\log{n})


我们可以看出上述算法在对操作集进行分治时,是基于数值分治的。而这一数值,实际上就是二分过程中的判定值 midmid。如果问题不具有可二分性,使得我们难以基于数值对操作集进行分治,我们是否可以找其他基准对操作集进行分治呢?

基于时间的离线分治

对于数据结构题,我们在回答每一个询问时,其本质就是计算初始数据和本次询问之前进行的所有修改对该询问造成的影响。如果题目允许离线算法,我们就可以预先知道所有操作组成的操作序列 QQ,那么我们是否可以运用与上文类似的思想对操作序列 QQ 进行分治呢?

P.S. 其实这就是 CDQ 分治

基本思想

假设共有 nn 项操作,我们定义函数 solve(l,r)solve(l, r),其功能为:k[l,r]\forall k \in [l, r],若第 kk 项操作为询问,则计算第 l(k1)l \sim (k - 1) 项操作对当前询问造成的影响。我们考虑采用如下方法进行计算:

  1. mid=12(l+r)mid = \frac{1}{2}(l + r)
  2. 递归地计算 solve(l,mid)solve(l, mid)
  3. 递归地计算 solve(mid+1,r)solve(mid + 1, r)
  4. 计算第 lmidl \sim mid 项操作中所有的修改对第 (mid+1)r(mid + 1) \sim r 项操作中所有询问造成的影响。

递归开始于 solve(1,n)solve(1, n),且递归结束于 l=rl = r 时(此时只有一项操作)。这里引用《算法竞赛进阶指南(第二版)》一书中对其正确性的证明:

设第 kk 项操作是询问,那么:

  • kmidk \le mid,则 solve(l,mid)solve(l, mid) 已经计算了第 l(k1)l \sim (k - 1) 项操作中所有修改对当前询问的影响;
  • k>midk > mid,则 solve(mid+1,r)solve(mid + 1, r) 已经计算了第 (mid+1)(k1)(mid + 1) \sim (k - 1) 项操作中所有修改对当前询问操作的影响。只要这一影响满足可加性且满足交换律,并且不同修改操作造成的影响互相独立,那么直接加上最后一项计算就可以得到第 l(k1)l \sim (k - 1) 项操作中所有修改对当前询问的影响。

这样做的好处是什么呢?我们发现,当我们在进行第 44 部分的计算时,我们其实是在解决一个静态问题。因此这一递归实质上可以把一个带有 nn 次操作的动态问题转换为解决 O(n)\mathcal{O}(n) 个静态问题,而原始问题中每个询问的结果是由 O(logn)\mathcal{O}(\log{n}) 个静态问题的结果共同组成的。一般来说,解决静态问题会比解决动态问题方便很多。与前面整体二分所类似地,只要我们能在只与 rlr - l (当前递归区间长度)有关,而与 nn 或者整个序列的长度无关的时间复杂度内解决 solve(l,r)solve(l, r),那么我们就可以用 O(f(n)logn)\mathcal{O}(f(n)\log{n}) 级别的复杂度内解决整个动态问题,其中 O(f(n))\mathcal{O}(f(n)) 是解决长度为 nn 的递归区间所需的复杂度。


CDQ 分治比较经典的应用就是偏序问题,接下来我们不妨从最简单的偏序问题看起。

我们首先来谈谈二维偏序问题。实际上逆序对就是二维偏序问题。我们可以把数值看成第一维 aa,下标看成第二维 bb,那么实际上我们求逆序对个数就是满足 ajai,bjai,ija_j \le a_i, b_j \le a_i, i \neq jjj 的个数,也就是二维偏序问题。

对于二维偏序问题,我们可以用归并排序求解,更可以用树状数组解决。那么对于三维乃至更高维的偏序问题呢?我们可以用二维树状数组!虽说如此,但是当 nn 达到 10510^5 的时候会爆内存的…… 这种时候,我们可以考虑对其进行“降维”以求解。

三维偏序问题

题面

nn 个元素,第 ii 个元素有 ai,bi,cia_i, b_i, c_i 三个属性。设 f(i)f(i) 表示满足 ajai,bjbi,cjci,ija_j \le a_i, b_j \le b_i, c_j \le c_i, i \neq jjj 的数量。

对于 d(0,n]d \in (0, n],求 f(i)=df(i) = d 的数量。

数据范围

1n1051 \le n \le 10^5

1ai,bi,ci2×1051 \le a_i, b_i, c_i \le 2 \times 10^5

题目链接

分析与实现

实际上,在本题中每一个三元组既是一次插入操作又是一次询问操作。

首先,我们考虑对所有三元组根据 aa 由小到大排序。由此,我们便可以保证在排序后的序列从左到右遍历时,对于位置 ii 而言第 0(i1)0 \sim (i - 1) 个三元组是满足 aa 上的限制条件的。接下来我们用 CDQ 分治求解:

  1. mid=12(l+r)mid = \frac{1}{2}(l + r)
  2. 递归地计算 solve(l,mid)solve(l, mid),这里 solvesolve 的功能与上面所讲的一样;
  3. 递归地计算 solve(mid+1,r)solve(mid + 1, r)
  4. 计算第 lmidl \sim mid 个元素对第 (mid+1)r(mid + 1) \sim r 个元素造成的影响(也就是贡献的偏序对数量)。

由于我们之前已经将原序列根据 aa 由小到大排过序了,因此我们可以确保第 44 步中第 lmidl \sim mid 个元素的 aa 一定是小于等于第 (mid+1)r(mid + 1) \sim r 个元素的 aa 的!由此一来,我们相当于将原问题降了一维,因为第 44 步的求解实际上就变成了一个逆序对问题,而且求解其的过程只与当前分治区间长度有关而不与整个序列长度有关。我们可以考虑用树状数组解决之。

另外需要注意的是,题目所要求的是小于等于而非严格小于,且不保证三元组互不相同。因此需要事先去重!时间复杂度为 O(nlog2n)\mathcal{O}(n\log^2{n}) 级别。

完整参考代码


假设数据范围不允许我们开高维树状数组,对于更高维的偏序问题该如何解决呢?既然泥萌都会树套树,我们这里也可以 CDQ 分治套 CDQ 分治啊~ 但是这样一来,对于 kk 维偏序问题,复杂度就变成了 O(nlogk1n)\mathcal{O}(n\log^{k - 1}n) 了。所以当 kk 比较大的时候还是去学 KD 树吧(然而我不会 QAQ)。不过,如果 kk 特别大,那还不如暴力 O(n2)\mathcal{O}(n^2) (逃…

四维偏序问题

题面

给定一个有 nn 个元素的序列,元素编号为 1n1 \sim n,每个元素有三个属性 a,b,ca, b, c,求序列中满足 i<j,ai<aj,bi<bj,ci<cji < j, a_i < a_j, b_i < b_j, c_i < c_j 的数对 (i,j)(i, j) 的个数。

数据范围

1n5×1041 \le n \le 5 \times 10^4

题目链接

分析与实现

显然该题的数据范围不允许我们开二维树状数组,所有我们考虑使用两层 CDQ 分治将原问题降低两个维度。

我们可以将原问题中的每一个元素看作一个四元组 id,a,b,c\langle id, a, b, c \rangle。对于第一层 CDQ 分治而言,每一个四元组同时对应一次插入操作和一次询问操作;而第二次 CDQ 分治实际上是用于解决第一层 CDQ 分治的第 44 步,也就是说我们只考虑左部修改对右部询问的影响,因此左部元素只对应一次插入操作,右部元素只对应一次询问操作。

需要注意的是,在第二层 CDQ 分治中我们按照 bb 这一维排序后 idid 这一维度的顺序会乱掉。因此在第一层 CDQ 分治中,在我们按照 aa 这一维排序后,趁着还满足第 lmidl \sim mid 中的 idid 一定小于 (mid+1)r(mid + 1) \sim r 中的 idid 之时,我们需要对每个元素所在的部分(左部或者右部)进行标记。由此一来,在第二层 CDQ 分治中,我们在处理修改时只处理 lmidl \sim mid 内有左部标记的元素;在处理询问时只处理有右部标记的元素,就可以同时满足两个维度上的限制条件。

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2019/01/28/offline-divide-and-conquer/