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

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