|
摘要 作者严正声名：本文比较沙雕。 另外，本文并不是“树套树入门”的文章，而是一篇议论性文章。议论性文章是指可能内容较受争议。 在我写这文章的时侯，输入法：蜀涛数，树桃树，树套数…… emm就是没有树套树？？？ 为什么写今天这篇文章呢，因为打了一道模板题，《二逼平衡树》。这题标签很简洁，树套树。于是Sshwy大菜鸡淦完这道题，一打开题解： 替罪羊树？vector？zkw？分块？二分？ 正所谓“平衡树的题怎么能用平衡树做呢”，由上述例子我们知道了“树套树的题怎么能用树套树做呢”，我们可以把这句话概括为套非套。咳。好吧，鉴于这个字有太深厚的底蕴我们还是改成桃非桃吧。  于是今天我们就这道模板题探究一下树桃树问题的各类算法，并对所用的结构性质做一些分析。 1 [LG3380]二逼平衡树
如果没有“区间”两个字，变成一个全局维护的问题，它就是一个普通平衡树问题。那么加上“区间”的限制，即要求我们能高效维护序列区间的同类信息，满足要求的数据结构很多。于是就有了树桃树的思路。广义上说，这不仅仅是树桃树的思路，可以说是结构桃结构的思路。但在具体讨论各个算法之前，容我先分析一下每个操作的性质。 1.1 查询排名查询一个数x的排名，我们可以理解为求区间[l,r]中处在值域[L,R]的数的个数。 这个问题是一个贡献性的问题。贡献性的问题可以被分解为若干子问题的和与差。注意，是和与差。它同样是一个离散的问题，假如你将数据离散化，那么查询排名的结果是不会变的。 1.2 查询第k小值查询第k小值，是一个具体的问题，这意味着你不能直接把数据离散化，不然查询的结果也会被离散化。而对于这样的具体问题，要么需要构造一个具体的结构去求解；要么就要把问题转化为一类离散问题求解，并牺牲一定的时间复杂度。 1.3 查询前驱后缀查询前驱后缀也是具体的问题。但是它和查询第k小值的区别在于，它还是一个可分解问题。尽管我们不能采用贡献的方式求前驱后继，但是我们可以求出若干个局部的前驱后继，然后取最优者。也就是说，我们可以将原问题划分为若干子问题，求得子问题的解后将他们合并出原问题的解。这个所谓的合并不单单指加法，还可以指Max,Min等操作。我将这样的特性称为可分解。 1.4 单点修改修改操作与查询操作不能比较，故不作叙述。 2 结构？分析问题的性质。如果没有“区间”二字，那么这是一个维护数集的问题。而“区间”体现的是序列的特征。 维护序列的问题，常用的算法结构有：树状数组、线段树、平衡树、分块、Vector、01TRIE。 维护数集的问题，常用的算法结构有：权值线段树、平衡树、分块、vector、01TRIE。 对你没有看错，我们将STL vector列入了常用算法结构。注意这是“维护”结构，因此算法应当是在线的，故我们不考虑整体二分。 3 某科学的非普通平衡树我们先讨论解决下面问题的复杂度。注意这并不是普通平衡树。
这其实是普通平衡树的弱化版。 设 A-B-C-D-E-F 分别表示查询排名/第k小值/前驱/后继，单点修改的复杂度。 当然，这道题有妥妥的平衡树做法。就不赘述了。接下来介绍几个具有代表性的平非平算法。并且注意，事实上处理分块，下面的其他算法都可以解决普通平衡树问题。 3.1 Vector好的现在你知道Vector算法的可行性了。  3.2 分块3.3 权值线段树3.4 01TRIE01TRIE的本质就是权值线段树。只不过01TRIE的二叉树更“偏”一些。权值线段树怎么做，01TRIE就怎么做。  4 某科学的区间信息维护那么现在我们考虑带有区间限制的问题。
这里我们讨论的是做为外桃结构的复杂度。如果你不使用桃算法，复杂度是不同的。 事实上，能够用结构桃结构算法的题目，通常要求这个问题能快速分解为若干个子问题，并快速将子问题的结构合并成原问题的答案（这里的“快速”通常只常数级别的时间）。接下来的讨论都基于这样的条件，因此我们不会考虑分解与合并问题答案的复杂度，而只考虑解决问题的复杂度。 设A(n),B(n),C(n),D(n),E(n)分别表示内层结构对于规模为n的全局问题，查询排名/第k小值/前驱/后继，单点修改的复杂度。 4.1 基于固定结构如果你的内层结构是固定的，意味着任意两个相同规模的同种结构是同构的。这类数据结构包括树状数组、线段树、分块、Vector、01TRIE。固定结构可以作差（如权值线段树作差），这有助于维护具体信息（比如第k小值）。那么接下来我们讨论一下外层结构的选择。 4.1.1 VectorVector做区间维护的话，差分？如果做差分的话修改就是线性的，否则查询就是线性的。鉴于原问题看上去查询操作较多，我们用差分吧。由于内层结构可以作差，意味着我们可以把问题分成两个问题作差。这样的总复杂度就是 看上去不错。 4.1.2 分块4.1.3 树状数组-线段树-01TRIE
4.1.4 平衡树利用平衡树维护区间时，单个结点代表元素，但是单个结点维护的信息代表整个子树（区间）。这时就涉及到了结点信息的合并问题，那么对内层结构而言也是一个合并问题，这显然大大增加时间复杂度，因此我们很少使用平衡树做为维护序列特征的外层结构。 4.2 基于动态结构内层基于动态结构，意味着具体问题（查询第k小值）无法快速构造具体结构求解。对于求第k小值而言，则通过二分转化为求排名，于是复杂度比求排名多一个log。我们仍然具体分析一下外层结构对复杂度的影响 4.2.1 Vector由于内层结构变动，那么所有具体问题（查询第k小值、前驱后继）都找不到具体结构。查询第k小值采用了二分的方式转化为离散问题，而查询前驱后继是不能用差分做的，因此也要转化为离散问题——即利用查询排名和k小值操作来求前驱后继。这时的复杂度就变成了
当然，还有一个方法，你可以选择Vector不做差分（大雾）  4.2.2 分块分块相比Vector就好很多了。查询第k小值仍需要二分排名，但查询前驱后继得益于他们的可分解性，可以用分块查询块内前驱后继，然后合并取最优解。因此复杂度为
4.2.3 树状数组这里就体现树状数组与线段树之间的差别了。树状数组同样依赖差分，因此要求问题具有可贡献性。此时它表现得就会和Vector一样差。但修改的复杂度依然好于Vector。
4.2.4 线段树-01TRIE同样的，得益于查询前驱后继的可分解性，线段树、01TRIE可以解决这类问题
4.2.5 平衡树不适合做外层结构。 5 非树套树算法之前我们只讨论了数据结构在个体在算法中的局部作用，接下来我们就考虑原问题的算法。 首先介绍两种桃非桃算法。 5.1 Vector为了维护区间信息，就不维护有序序列了，直接现场找。需要注意的是，查询排名是线性的。 查询第k小可以用快排的思想做到线性复杂度。方法概括起来就是一个二分，但是每次二分后问题规模缩小一半，所以期望复杂度是线性的。
5.2 分块
6 序列套数集如果你看懂了上文两个科学的章节以及它们的联系，那么接下来的内容就基本可以忽略了。如果没有看懂（或者我的叙述有问题），那么接下来我将介绍一些常见的结构桃结构的具体算法做为例子。外层结构用于维护序列特征（区间），而内层结构维护数集信息（值域）。 6.1 树状数组这算是很常用的一种做法。笔者使用的就是树状数组套权值线段树的算法。 6.1.1 套权值线段树-01TRIE权值线段树是固定结构，满足贡献性。查询排名，k小值都转化为权值线段树的二分，维护log个结点一起跳即可。喜闻乐见的算法。
6.2 线段树-01TRIE这两种外层结构可以解决可分解性的问题，比树状数组的适用性更强。套权值线段树-01TRIE是肯定能做的，因此就不讲这两种了，讲一种比较偏的。 6.2.1 套Vector
我相信没人这么写 好吧我错了，洛谷上有人用zkw套vector过了 有人问，为什么不套平衡树？原因很简单。前文我们花大量篇幅讲内层使用变动结构的坏处，所以我们自然不会选择平衡树做为内层结构。有兴趣的同学可以下来自己研究复杂度。 7 数集套序列我们可以反过来套啊！外层维护权值，内层维护区间。对于外层的数据结构，维护某个值域下的下标序列，对内层结构，维护对下标序列的查询修改。 7.1 权值线段树-01TRIE外层权值线段树维护权值，插入每个数时，在路径的结点上记录他们的下标，这样每个结点就有若干下标组成序列。于是问题转化为标记的查询修改问题。 同样的，我们只讲权值线段树做法。 7.1.1 套Vector
7.1.2 套线段树-01TRIE-树状数组
8 扩展-懵逼平衡树二逼平衡树的问题是一个非平衡树问题。因为其涉及的操作并没有违背序列特征。它的修改操作不会改变结构。那么如果我们将修改操作改成插入删除操作呢？
插入，是指在两个元素之间增加一个元素。插入删除是具有数集特征的操作，而区间则是具有序列特征的限制，现在要求我们同时处理这两个条件。 8.1 非嵌套算法我们仍然考虑一些非传统算法。 8.1.1 Vector不得不说Vector是一个强有力的算法。利用Vector本身支持的插入删除操作，利用快排的思想，仍然可以在
的时间内解决问题。 8.2 嵌套算法接下来考虑桃算法。分析问题的特征。原问题要求维护插入删除的数集操作，又要维护区间查询的序列操作。 8.2.1 平衡树在前文所述，平衡树一直是动态结构而不适合做嵌套结构。在这里，利用在序列中的位置做键值，可以方便地维护一个动态序列。这里的平衡树多指Splay或Treap。 解决了插入删除操作，接下来考虑询问。利用平衡树的分割合并操作找到区间对应的子平衡树，然后？？？你发现这个平衡树结构就没什么用了。得在结点上维护一个内层结构，比如线段树-01TRIE之类的。而在平衡树向上合并信息的时侯还得写一个线段树合并之类的东西。 为什么会出现这样的繁琐算法？因为平衡树它只维护了区间的特征，它以位置为键值，保证了按序列的顺序。但是这样就忽略了数集的特征，使得你需要在内套一个维护数集的结构，也就是线段树之类的结构以解决问题。得益于平衡树的特性，你的数据结构又需要高效合并，最终使得整个算法十分可怕。 但是别忘了，我们可以数集套序列！ 8.2.2 数集套序列外层结构维护值域，内层结构维护位置。我们知道值域是固定的，因此可以用权值线段树-01TRIE。那么我们的问题就变成了：
但是这个问题并不好做。因为插入一个数会使得后面的数下标发生改变。如果修改所有标记的话复杂度将极高。这里我们有两种方式维护。 8.2.2.1 套平衡树
8.3 值域分块
8.3.1 不带区间限制
8.3.2 块链套分块
9 总结好的。讲到最后，你发现这个套是真的很有趣，它能展现出许多结构之间的共性。
利用结构之间的共性，能够发现很多算法之间是同源的。希望大家能真正理解这其中的原理。知道了这一点，在下次做数据结构题的时侯可以有一个更全方位的思路。学习算法时也要多总结，不要只限于死记硬背。深刻理解他们的通性与差异，可以帮助你选择合适的结构解题。 10 后记如果大家喜欢这篇文章，希望大家关注我的博客 ，并关注我的博客转型计划～
|
|
|
