从树套树浅析常用结构的特性

摘要

2019.6.18 编入精选文章

作者严正声名:本文比较沙雕。

另外,本文并不是 “树套树入门” 的文章,而是一篇议论性文章。议论性文章是指可能内容较受争议。

在我写这文章的时侯,输入法:蜀涛数,树桃树,树套数……

emm 就是没有树套树???

所谓树套树,套是什么意思?建议自行百度(注意不是谷歌是百度)。

为什么写今天这篇文章呢,因为打了一道模板题,《二逼平衡树》。这题标签很简洁,树套树。于是 Sshwy 大菜鸡淦完这道题,一打开题解:

替罪羊树?vector?zkw?分块?二分?

正所谓“平衡树的题怎么能用平衡树做呢”,由上述例子我们知道了“树套树的题怎么能用树套树做呢”,我们可以把这句话概括为套非套。咳。好吧,鉴于这个字有太深厚的底蕴我们还是改成桃非桃吧。

于是今天我们就这道模板题探究一下树桃树问题的各类算法,并对所用的结构性质做一些分析。

[LG3380]二逼平衡树

维护一个序列,支持区间查询排名 / 第 k 小值 / 前驱 / 后继,支持单点修改。

如果没有 “区间” 两个字,变成一个全局维护的问题,它就是一个普通平衡树问题。那么加上 “区间” 的限制,即要求我们能高效维护序列区间的同类信息,满足要求的数据结构很多。于是就有了树桃树的思路。广义上说,这不仅仅是树桃树的思路,可以说是结构桃结构的思路。但在具体讨论各个算法之前,容我先分析一下每个操作的性质。

查询排名

查询一个数 x 的排名,我们可以理解为求区间 中处在值域 的数的个数。

这个问题是一个贡献性的问题。贡献性的问题可以被分解为若干子问题的和与。注意,是和与。它同样是一个离散的问题,假如你将数据离散化,那么查询排名的结果是不会变的。

查询第 k 小值

查询第 k 小值,是一个具体的问题,这意味着你不能直接把数据离散化,不然查询的结果也会被离散化。而对于这样的具体问题,要么需要构造一个具体的结构去求解;要么就要把问题转化为一类离散问题求解,并牺牲一定的时间复杂度。

查询前驱后缀

查询前驱后缀也是具体的问题。但是它和查询第 k 小值的区别在于,它还是一个可分解问题。尽管我们不能采用贡献的方式求前驱后继,但是我们可以求出若干个局部的前驱后继,然后取最优者。也就是说,我们可以将原问题划分为若干子问题,求得子问题的解后将他们合并出原问题的解。这个所谓的合并不单单指加法,还可以指 Max,Min 等操作。我将这样的特性称为可分解。

单点修改

修改操作与查询操作不能比较,故不作叙述。

结构?

分析问题的性质。如果没有 “区间” 二字,那么这是一个维护数集的问题。而 “区间” 体现的是序列的特征。

维护序列的问题,常用的算法结构有:树状数组、线段树、平衡树、分块、Vector、01TRIE。

维护数集的问题,常用的算法结构有:权值线段树、平衡树、分块、vector、01TRIE。

对你没有看错,我们将 STL vector 列入了常用算法结构。注意这是 “维护” 结构,因此算法应当是在线的,故我们不考虑整体二分。

某科学的非普通平衡树

我们先讨论解决下面问题的复杂度。注意这并不是普通平衡树。

维护一个序列,支持查询全局的排名 / 第 k 小值 / 前驱 / 后继,支持单点修改。

这其实是普通平衡树的弱化版。

分别表示查询排名 / 第 k 小值 / 前驱 / 后继,单点修改的复杂度。

当然,这道题有妥妥的平衡树做法。就不赘述了。接下来介绍几个具有代表性的平非平算法。并且注意,事实上处理分块,下面的其他算法都可以解决普通平衡树问题。

Vector

先考虑用它维护全局问题。我们直接用它维护一个有序序列。那么排名可以二分查询;第 k 小值、前驱后继都可以以常数时间做完。单点修改后需要我们维护序列的有序性,复杂度是线性的。

那么 Vector 的复杂度为 。(乍一看这玩意儿复杂度还不错)

至于为什么会有这样的平非平算法

好的现在你知道 Vector 算法的可行性了。

分块

设块大小为 T,预处理块内排序。注意这是一个全局的查询,因此没有所谓的边角操作。

查询排名,可以在块内二分,复杂度 。查询第 k 小值可以二分排名,复杂度 . 前驱后继可以直接在块内二分,复杂度 。修改操作可以直接修改,然后做一次插入排序。复杂度

,复杂度为

注意 .

权值线段树

查询排名和第 k 小值,都可以在权值线段树上二分;前驱后继也可以用前两个操作完成。

修改操作也是 的。

总复杂度

01TRIE

01TRIE 的本质就是权值线段树。只不过 01TRIE 的二叉树更 “偏” 一些。权值线段树怎么做,01TRIE 就怎么做。

01TRIE and Segment Tree

复杂度

某科学的区间信息维护

那么现在我们考虑带有区间限制的问题。

维护一个序列支持区间查询排名 / 第 k 小值 / 前驱 / 后继,支持单点修改。

这里我们讨论的是做为外结构的复杂度。如果你不使用桃算法,复杂度是不同的。

事实上,能够用结构桃结构算法的题目,通常要求这个问题能快速分解为若干个子问题,并快速将子问题的结构合并成原问题的答案(这里的 “快速” 通常只常数级别的时间)。接下来的讨论都基于这样的条件,因此我们不会考虑分解与合并问题答案的复杂度,而只考虑解决问题的复杂度。

分别表示内层结构对于规模为 n 的全局问题,查询排名 / 第 k 小值 / 前驱 / 后继,单点修改的复杂度。

基于固定结构

如果你的内层结构是固定的,意味着任意两个相同规模的同种结构是同构的。这类数据结构包括树状数组、线段树、分块、Vector、01TRIE。固定结构可以作差(如权值线段树作差),这有助于维护具体信息(比如第 k 小值)。那么接下来我们讨论一下外层结构的选择。

Vector

Vector 做区间维护的话,差分?如果做差分的话修改就是线性的,否则查询就是线性的。鉴于原问题看上去查询操作较多,我们用差分吧。由于内层结构可以作差,意味着我们可以把问题分成两个问题作差。这样的总复杂度就是

看上去不错。

分块

分块要考虑分块大小的问题。设大小为 T,对于每个块内的问题规模就是 T。我们假设边角暴力的复杂度不高于线性,并且单点修改的复杂度不高于线性。则分块算法的复杂度是

对于分块取值的问题,通常满足

的 T 是较合适的值。

树状数组 - 线段树 -01TRIE

树状数组将问题分为 个区间的加减;而线段树与 01TRIE 将问题分为 个区间的和;

这些数据结构都将问题转化为 个子问题求解。而修改的时侯也会在 个结点上修改。复杂度为

平衡树

利用平衡树维护区间时,单个结点代表元素,但是单个结点维护的信息代表整个子树(区间)。这时就涉及到了结点信息的合并问题,那么对内层结构而言也是一个合并问题,这显然大大增加时间复杂度,因此我们很少使用平衡树做为维护序列特征的外层结构。

基于动态结构

内层基于动态结构,意味着具体问题(查询第 k 小值)无法快速构造具体结构求解。对于求第 k 小值而言,则通过二分转化为求排名,于是复杂度比求排名多一个 log。我们仍然具体分析一下外层结构对复杂度的影响

Vector

由于内层结构变动,那么所有具体问题(查询第 k 小值、前驱后继)都找不到具体结构。查询第 k 小值采用了二分的方式转化为离散问题,而查询前驱后继是不能用差分做的,因此也要转化为离散问题——即利用查询排名和 k 小值操作来求前驱后继。这时的复杂度就变成了

当然,还有一个方法,你可以选择 Vector 不做差分(大雾)

分块

分块相比 Vector 就好很多了。查询第 k 小值仍需要二分排名,但查询前驱后继得益于他们的可分解性,可以用分块查询块内前驱后继,然后合并取最优解。因此复杂度为

树状数组

这里就体现树状数组与线段树之间的差别了。树状数组同样依赖差分,因此要求问题具有可贡献性。此时它表现得就会和 Vector 一样差。但修改的复杂度依然好于 Vector。

线段树 -01TRIE

同样的,得益于查询前驱后继的可分解性,线段树、01TRIE 可以解决这类问题

平衡树

不适合做外层结构。

非树套树算法

之前我们只讨论了数据结构在个体在算法中的局部作用,接下来我们就考虑原问题的算法。

首先介绍两种桃非桃算法。

Vector

为了维护区间信息,就不维护有序序列了,直接现场找。需要注意的是,查询排名是线性的。

查询第 k 小可以用快排的思想做到线性复杂度。方法概括起来就是一个二分,但是每次二分后问题规模缩小一半,所以期望复杂度是线性的。

于是总复杂度是 .

分块

设块大小为 T,预处理块内排序。查询排名,可以在块内二分,边角暴力,复杂度 。查询第 k 小值可以二分排名,边角暴力,复杂度 . 前驱后继可以直接在块内二分,边角暴力,复杂度 。修改操作可以直接修改,然后做一次插入排序。复杂度

,复杂度为

注意, .

序列套数集

如果你看懂了上文两个科学的章节以及它们的联系,那么接下来的内容就基本可以忽略了。如果没有看懂(或者我的叙述有问题),那么接下来我将介绍一些常见的结构结构的具体算法做为例子。外层结构用于维护序列特征(区间),而内层结构维护数集信息(值域)。

树状数组

这算是很常用的一种做法。笔者使用的就是树状数组套权值线段树的算法。

套权值线段树 -01TRIE

权值线段树是固定结构,满足贡献性。查询排名,k 小值都转化为权值线段树的二分,维护 log 个结点一起跳即可。喜闻乐见的算法。

复杂度

由于权值线段树、01TRIE 其实本质都是维护权值,所以 01TRIE 我也不解释了。

线段树 -01TRIE

这两种外层结构可以解决可分解性的问题,比树状数组的适用性更强。套权值线段树 -01TRIE 是肯定能做的,因此就不讲这两种了,讲一种比较偏的。

套 Vector

这并不是不是不行,只是感觉莫名其妙的算法。用 Vector 维护有序的序列。

  1. 查询排名,就查询比它小的数的个数。由于区间被分为 log 个区间的加减,于是可以在每个区间上直接查询排名,复杂度
  2. 查询第 k 小,可以二分查询排名,复杂度
  3. 查询前驱可以在 log 个 Vector 上查询局部前驱取最优,复杂度 。同理查询后缀就不说了。
  4. 修改的时侯,虽然有 log 个 Vector 需要修改,但是它们的元素总数是 的,因此复杂度也是 .

复杂度 .

我相信没人这么写

好吧我错了,洛谷上有人用 zkw 套 vector 过了

有人问,为什么不套平衡树?原因很简单。前文我们花大量篇幅讲内层使用变动结构的坏处,所以我们自然不会选择平衡树做为内层结构。有兴趣的同学可以下来自己研究复杂度。

数集套序列

我们可以反过来套啊!外层维护权值,内层维护区间。对于外层的数据结构,维护某个值域下的下标序列,对内层结构,维护对下标序列的查询修改。

权值线段树 -01TRIE

外层权值线段树维护权值,插入每个数时,在路径的结点上记录他们的下标,这样每个结点就有若干下标组成序列。于是问题转化为标记的查询修改问题。

同样的,我们只讲权值线段树做法。

套 Vector

这不是不行。用 Vector 始终维护一个有序序列。

  1. 对于查询 x 在区间 [l,r] 中的排名,相当于查询值域在 ,区间处于 的数的个数。于是问题转化为在 log 个 Vector 中查询处于 的数的个数,复杂度仍为
  2. 而在查询第 k 小值时,我们可以在 的时间中查询一个结点中下标处于 的数的个数。因此可以直接在树上二分,复杂度
  3. 查询前驱,可以查询值域在 ,区间处于 [l,r] 的最大的数,这可以二分做,复杂度 ,也可以直接用前两个操作求前驱。后继同理。
  4. 最后,修改操作需要删除标记添加标记,做插入排序,问题的总规模的线性的,因此复杂度 .

总复杂度 。比序列桃数集的情况好了一点。

套线段树 -01TRIE- 树状数组

这也是标准做法之一了。

  1. 内层线段树维护标记,查询排名是 的。
  2. 查询第 k 小值用二分做,复杂度
  3. 前驱后继可以二分可以用之前的操作,复杂度都是
  4. 修改则是在 log 个线段树上修改,复杂度

总复杂度 .

01TRIE、树状数组我也不多解释了。都知道怎么做的。(其实我也是现在才发现内层可以套树状数组)

扩展 - 懵逼平衡树

二逼平衡树的问题是一个非平衡树问题。因为其涉及的操作并没有违背序列特征。它的修改操作不会改变结构。那么如果我们将修改操作改成插入删除操作呢?

维护一个序列,支持区间查询排名 / 第 k 小值 / 前驱 / 后继,支持在单点插入 / 删除。

插入,是指在两个元素之间增加一个元素。插入删除是具有数集特征的操作,而区间则是具有序列特征的限制,现在要求我们同时处理这两个条件。

非嵌套算法

我们仍然考虑一些非传统算法。

Vector

不得不说 Vector 是一个强有力的算法。利用 Vector 本身支持的插入删除操作,利用快排的思想,仍然可以在

的时间内解决问题。

嵌套算法

接下来考虑桃算法。分析问题的特征。原问题要求维护插入删除的数集操作,又要维护区间查询的序列操作。

平衡树

在前文所述,平衡树一直是动态结构而不适合做嵌套结构。在这里,利用在序列中的位置做键值,可以方便地维护一个动态序列。这里的平衡树多指 Splay 或 Treap。

解决了插入删除操作,接下来考虑询问。利用平衡树的分割合并操作找到区间对应的子平衡树,然后???你发现这个平衡树结构就没什么用了。得在结点上维护一个内层结构,比如线段树 -01TRIE 之类的。而在平衡树向上合并信息的时侯还得写一个线段树合并之类的东西。

为什么会出现这样的繁琐算法?因为平衡树它只维护了区间的特征,它以位置为键值,保证了按序列的顺序。但是这样就忽略了数集的特征,使得你需要在内套一个维护数集的结构,也就是线段树之类的结构以解决问题。得益于平衡树的特性,你的数据结构又需要高效合并,最终使得整个算法十分可怕。

但是别忘了,我们可以数集套序列!

数集套序列

外层结构维护值域,内层结构维护位置。我们知道值域是固定的,因此可以用权值线段树 -01TRIE。那么我们的问题就变成了:

  1. 查询区间排名:查询在 log 个值域结点上,标记位于 的标记个数。
  2. 查询区间第 k 小值:在权值线段树上二分
  3. 查询前驱后继:在权值线段树上二分
  4. 插入删除:在权值路径上的结点增加标记,删除标记

但是这个问题并不好做。因为插入一个数会使得后面的数下标发生改变。如果修改所有标记的话复杂度将极高。这里我们有两种方式维护。

套平衡树

在每个结点上用平衡树维护标记。每个标记具有一个属性 idx,表示这个标记的下标。平衡树以属性 idx 做为键值。查询操作该怎么查就怎么查。在位置 x 的前面插入一个数 v,我们先分割出键值大于等于 x 的一棵子平衡树,然后打一个 “键值加一” 的 tag。这样每次只要我们先下传 tag 就能保证正确性。删除同理。

除了打 Tag 的方式,我们还可以维护二元组的平衡树。 表示在位置 x 前插入的第 y 个数。 表示这个位置本身的数。那么插入删除就可以很自然地进行。每次查询的时侯,需要将给出的 转化为二元组区间。我们可以维护一个前缀和 表示前 i 个位置的数的个数(我们假装插入的数不占位置)。前缀和用树状数组维护,可以 二分查找到二元组区间的位置。然后再做查询即可。

两种做法的复杂度都是

值域分块

最后,讲一个比较偏的算法。维护值域,能不能分块?能!按值域分块,假设分块大小为 T。第 i 块代表的值域是

不带区间限制

循序渐进。我们先考虑下列问题的分块求解

维护一个序列,支持查询排名 / 第 k 小值 / 前驱 / 后继,支持在单点插入 / 删除。

这 TM 不就是普通平衡树吗。我们维护两个数组, 表示值域在 的数的个数; 表示值为 i 的数的个数。

考虑一下各个操作:

  1. 查询排名:即查询比它小的数的个数,那么先查 S 数组,边角就查 C 数组,复杂度
  2. 查询第 k 小值:先依次累加 S 数组,发现大于 k 了就改成累加 C 数组,复杂度
  3. 查询前驱后继:先查与它相邻的块域内是否有数,找到有数的块域后再查 C 数组。复杂度
  4. 插入删除:复杂度

,则复杂度为

块链套分块

接下来考虑原问题。带上了区间限制怎么办?考虑块状链表。每个块状链表内部维护值域分块。同时,我们改成维护前缀和。链表中当前块的 表示之前所有块(包括当前块)中,权值在 的数的个数; 表示之前所有块(包括当前块)中,权值为 i 的数的个数。于是,我们可以简单地差分出当前区间内的整块的 S,C 数组。对于零碎的块暴力统计即可。我们还是仔细说一下:

  1. 查询排名:整块就用分块的方法查,边角的暴力,复杂度
  2. 查询第 k 小值:整块用分块的方法,边角的可以先全部加到当前的 S,C 数组中,查完了再还原。复杂度
  3. 查询前驱后继:整块就用分块的方法查,边角的暴力,复杂度
  4. 插入 / 删除:链表里找位置的复杂度是 ,插入的复杂度
  5. 维护块链:合并相邻块时,因为我们取的是前缀和,因此其他的前缀和不受影响,只需要把元素合并,而维护 S,C 不变。复杂度 ;分割时,要对两个新块内的元素重建 S,C 数组,复杂度 .

我们假设值域与下标同阶。那么取 ,可得总复杂度为

总结

好的。讲到最后,你发现这个是真的很有趣,它能展现出许多结构之间的共性。

  1. 树状数组维护具有贡献性的信息,局限性较强,但好写。
  2. 线段树维护多类信息,用途广,但是是固定结构。
  3. 01TRIE 与线段树同源。
  4. 平衡树维护可以高效合并的信息,并能维护动态结构问题。
  5. 分块能方便地维护固定线性结构的信息,常数较小。
  6. 块状链表则比较偏门,真正用到的地方较少。
  7. Vector 什么都能干。

利用结构之间的共性,能够发现很多算法之间是同源的。希望大家能真正理解这其中的原理。知道了这一点,在下次做数据结构题的时侯可以有一个更全方位的思路。学习算法时也要多总结,不要只限于死记硬背。深刻理解他们的通性与差异,可以帮助你选择合适的结构解题。

后记

如果大家喜欢这篇文章,希望大家关注我的博客 ,并关注我的博客转型计划~


 上一篇
线段树与历史区间最值问题 线段树与历史区间最值问题
摘要 读 jry《区间最值操作与历史最值问题》 前言仍然是线段树的应用问题。在前文中我们探讨了线段树的基及其应用。如果对这方面了解较少的同学请移步《线段树初步》、《线段树应用》。本文将继续讲解线段树在区间最值与历史最值问题上的应用。 区间
2019.06.19
下一篇 
最短路应用 最短路应用
摘要 本文接上文 最短路算法,为大家介绍最短路的常见应用。 将原来打的各种题目的零散文章汇总,编入精选文章。 负环与差分约束一个看起来不像最短路的最短路应用。给出一组差分约束,问是否有解。差分约束是形容
2019.06.15
  目录