关键词：
树套树，顾名思义，就是用一颗树套在另外一组树之上。比方说我们有一颗树，假如它的每一个结点（抽象意义上，一株树由多个结点组成）也是一株树，那么这就形成了树套树。外部树和内部树可以是不同品种的。一般外部树都是形如线段树或树状数组等用于统计和区间处理但是内存消耗大的树，而内部树则往往是像Splay一样功能强大且内存消耗小的树，当然这不是绝对的。
考虑这样的一个场景，给你一组数值序列S={v1,v2,....}，要求你快速求区间[L,R]之间第k小的值，并且数值序列中可能有若干元素会被修改。如何解决？首先我们建立一株线段树，线段树内每个区间（对应原线段树结点）均用Splay树维护，区间[x,y]对应的Splay树用于保存子序列S[x...y]中的值。显然一次更新操作，我们只需要更新log2(n)个区间，对应的也就是log2(n)个区间，更新操作可以用删除原Splay结点并插入一个新的结点来实现，因此一次操作的空间复杂度为O(log2(n))，当然时间复杂度为O(log2(n)*log2(n))。而一次询问操作，我们只需要对可能的值做二分查找，因此问题就转化成了询问S[L...R]中小于某个特定值v的值数目。而具体的实现是，对于线段树我们仅查找区间[L,R]下对应的多棵Splay树，统计每一株树中小于v的结点数目，就可以得到正确结果。因此询问操作时间复杂度为O(log2(|V|))*log2(n)*log2(n))。其中V表示值域，由于值域较难控制，我们也可以选择用线段树维护值信息，而用Splay维护区间统计信息，这样时间复杂度就为O((log2(n))^3)，但是这一般需要提前对数据（包括初始数据和后面修改的所有数据）进行预先离散化处理，相应的消耗的空间也会更大。
也许你会问，为什么要用Splay树作为内部树，Splay树在上面场景中不就是用于统计区间信息吗，为什么不直接使用线段树套线段树呢。这是因为在创建外部树时，我们就会创建内部结点，而如果内部结点是空Splay树，每个结点消耗的空间都是常数，如果是线段树，那么消耗的空间就是O(n)，这样由于外部树有O(n)个内部树结点，而每棵内部树的空间复杂度都是O(n)，那么空间复杂度将达到O(n^2)。当然你可以选择先建立一株空树，之后多株线段树在空树的基础上进行可持久化修改，这样初始化的空间复杂度与线段树套Splay树一致，但是每次后续修改操作其花费的空间复杂度为O(log2(n)*log2(n))，比线段树套Splay树的O(log2(n))要大。
树套树的玩法应该还有很多，以后遇到了再补上。
树套树初探(代码片段)
最近学了学树套树，做了几道模板题。发现好像有点水咳咳咳。树套树，顾名思义，一个树套一个树。比如树状数组套平衡树，就是把树状数组的每一个结点作为一颗平衡树，线段树套权值线段树，就是一颗线段树，每一个结点... 查看详情
树套树(代码片段)
树套树一种思想，就是一棵树的节点是另一颗树。在外面的叫外层树，在里面的叫内层树。外层树一般是，树状数组，线段树内层树一般是平衡树，STL,线段树线段树套STL/**@Author:zhl*@Date:2020-11-1612:50:32*/#include<bits/stdc++.h>#define... 查看详情
树套树三题题解
...这题数据非常水……从O(nlogn)的主席树到O(nlog3n)的树套树+二分到O(nsqrt(n)log2n)的分块套二分套二分到O(n2)的暴力都能过……)鉴于这就是动态排名系统的静态版，就不说了，贴代码：线段树套平衡树：#include 查看详情
uvalive-6709树套树(代码片段)
...法：暴力可过，建n颗线段树暴力更新，但是正解应该是树套树，树套树需要注意的是当建树或修改时pushup操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过... 查看详情
树套树乱讲
树套树乱讲树状数组套线段树先学会主席树。主席树可以被理解为一个二维平面，其中n棵树可以视作横轴，每棵树中的坐标范围（也就是线段树的坐标范围）可以视作纵轴。这样一来就是用主席树维护了一些在二维平面上的点... 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情
树套树乱讲的代码(代码片段)
树套树乱讲的代码由于部分代码的完成时间较早所以码风可能有些差异，敬请谅解。动态区间Kth题面整体二分题解#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>usingnamespacestd;constintN=10005 查看详情
洛谷p3380模板二逼平衡树（树套树）
洛谷P3380【模板】二逼平衡树（树套树）线段树套treap:就是线段树每个节点放一个treap。建树复杂度应该是$nlogn$，操作1,3,4,5的复杂度是$(logn)^2$，操作2的复杂度是$(logn)^3$。操作3：找到线段树的对应叶子节点后找到要删除的值，... 查看详情
hdu4819mosaic树套树(代码片段)
...点变成这个矩形中最大值和最小值的平均数思路很显然的树套树啊就是一开始傻逼了没想到怎么去维护这个东西其实很简单对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度(O(log(n)))voidmodify_y(intt,intl... 查看详情
[bzoj720][jzyzoj2016]gty的妹子树强制在线树分块/树套树
jzyzoj的p2016先码着,强制在线的树分块或者树套树?关键是我树分块还在入门阶段树套树完全不会啊摔 http://blog.csdn.net/jiangyuze831/article/details/41445003果然我除了抄代码什么也不会......树分块之类的东西完全不会计算复杂度.....似... 查看详情
bzoj3196树套树模板
...于解开了区间第k大的心结。。。 比较裸的线段树套平衡树，比较不好想的是求区间第k大时需要二分一下答案，然后问题就转化为了第一个操作。复杂度nlog3n。跑的比较慢。。。 在查前驱后继的时候写错了。。... 查看详情
树套树day2
滚回来更新,,,在Day1我们学了最基本的线段树套平衡树Day2开始我们要学习一些黑科技（所以很大概率会出现Day3w1.线段树上的黑科技 这一段我们分几项来讲1.权值线段树 权值线段树以权值为下标建树（就像求逆序对时... 查看详情
bzoj2141排队[国家集训队2011]排队(魏铭)树套树线段树套替罪羊树
这个题就是动态偏序对，每次操作做两个删除两个插入就好了。#include<cstdio>#include<iostream>#include<cstring>#defineMAXN100010usingnamespacestd;typedeflonglongLL;typedefdoubleD;constDa=0.756;LLans;structScapeGoat 查看详情
luogu3380模板二逼平衡树（树套树）
#include<iostream>#include<cstdlib>#include<cstdio>#include<ctime>usingnamespacestd;intn,m,cnt,a[50005],rot[200005],opt,ans,uu,vv,ww;structNode{intl,r,siz,hav,val,rnd;}nd[40000 查看详情
「题解」树套树tree(代码片段)
本文将同步发布于：洛谷博客；csdn；博客园；简书。题目题目描述给你一个\\(n\\)个点的小树（正常的树），给你一个\\(m\\)个点的大树，大树的节点是一棵小树，大树的边是跨越了两棵小树之间的边，\\(q\\)次询问，求树上距离... 查看详情
bzoj3196二逼平衡树树套树
3196:Tyvj1730二逼平衡树TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 3776 Solved: 1483Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：1.查询k在区间内的排名2.查... 查看详情
bzoj3196[tyvj1730]二逼平衡树树套树线段树套scapegoat_tree
人傻自带大常数#include<cstdio>#include<cstring>#include<iostream>#defineMAXN1500005usingnamespacestd;constdoubleA=0.756;constintinf=100000000;intn,m,a[50005];structScapeGoat_Tree{ScapeGoat_ 查看详情
树套树+uvalive6709mosaic二维线段树
题目链接：6709Mosaic 题解：参考这个博客:二维线段树，先按行建树然后每一个节点也是一个棵线段树按列建。#include<bits/stdc++.h>#include<cmath>#include<set>#include<cstdio>#include<iomanip>#include<iostream># 查看详情