摘要

作者严正声名：本文比较沙雕。本文全程口糊

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

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

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)。（乍一看这玩意儿复杂度还不错）

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

好的现在你知道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 后记

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