[树套树学习笔记]()

一、线段树/树状数组套平衡树

既然是“线段树套平衡树” ，就先建一颗线段树：

它的每个结点都是一颗平衡树，这颗平衡树就维护该节点所表示的区间：

但是线段树的每个结点都套一颗平衡树，空间会不会炸呢？

可以把线段树分为若干层：

可以发现，线段树的每一层表示的节点数都是 O(n) 的，一颗线段树有 O(logn) 层，所以所以平衡树的结点数之和是 O(nlogn) 的。

也可以这样想，如图：

可以发现每个下标（上图以下标 4 为例）都只被线段树上 O(logn) 个节点包含，一共有 n 个下标，所以线段树套平衡树的空间复杂度是 O(nlogn) 。

接下来就是应用了。。以经典的一道题 BZOJ3196 二逼平衡树为例：

题意：

给你一个序列，要支持以下 5 种操作：

n,m<=50000 ，序列中的数的范围为 [0,10^8] ，时限 10s 。

题解：

首先当然是要把树建好；
对于操作 1 ，询问区间内一个数的排名，就是在线段树中找到所以对应区间，询问在这个区间内比 k 小的数的个数，最后把这些询问一加然后再 +1 即可。下图以 l=1,r=5,k=4 为例：

根据线段树的性质，一个区间可以由线段树上 O(logn) 个子区间拼成，在平衡树上询问小于 k 的数的个数的时间复杂度为 O(logn) ，所以操作 1 的总时间复杂度是 O(log^2n)；
对于操作 2 ，我们发现询问区间第 k 大在线段树上并不能完成合并。考虑二分答案这个数，用操作 1 判定这个数是否在区间内排在第 k 名。二分的范围是 [0,10^8] ，所以这个操作的时间复杂度为 O(log10^8\cdot log^2n) 。
在二分过程中需注意，在二分中心的名次等于 k 时要向右二分，因为我们要找到最大的满足要求的值。下图以 l=1,r=5,k=5 为例：

由图可知，有 5,6,7 这三个名次为 5 的值，而只有 7 是我们所求得答案；

对于操作 4,5