关键词：
树套树乱讲
树状数组套线段树
先学会主席树。
主席树可以被理解为一个二维平面，其中n棵树可以视作横轴，每棵树中的坐标范围（也就是线段树的坐标范围）可以视作纵轴。这样一来就是用主席树维护了一些在二维平面上的点，给定\(a,b,c,d\)，可以在\(O(\logn)\)的时间内求出满足\(a\le x_i\le b,c\le y_i\le d\)的\(i\)的数量。
而树状数组套线段树就是把这个问题动态化。
对于上述的问题，我们是通过对主席树直接维护前缀和，查询时两棵主席树相减，再在区间\([c,d]\)上查询答案的。既然已经维护了前缀和，那么一个单点修改就会涉及到\(n\)棵主席树从而使修改的时间复杂度炸裂。
那么现在我们就考虑用更为灵活的树状数组来维护前缀和。
把主席树的前缀和用树状数组的形式表示，每次单点修改时在\(\logn\)棵线段树上修改，查询时也是在\(\logn\)棵线段树上查。
时间复杂度\(O(n\log^2n)\)
动态区间Kth
支持数组的单点修改，区间查Kth
单点修改就是树状数组的单点修改。
用树状数组维护前缀和，这时一个区间可以用\(\logn\)棵线段树与\(\logn\)棵线段树作差的形式来表示。
在线段树上二分，复杂度\(O(n\log^2n)\) 代码1.9k
三位偏序（陌上花开）
第一维排序第二维树状数组第三维权值线段树
做完了，代码1.5k
【模板】二逼平衡树
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1、查询k在区间内的排名
2、查询区间内排名为k的值
3、修改某一位值上的数值
4、查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)
5、查询k在区间内的后继(后继定义为严格大于x，且最小的数，若不存在输出2147483647)
树状数组套线段树。
1、查k的排名就是查区间内\([1,k-1]\)的数的个数+1
2、排名为k的值，见动态区间Kth
3、树状数组修改
4、相当于操作二查排名为“\([1,k-1]\)内数的个数”的值
5、相当于操作二查排名为“\([1,k]\)内数的个数+1”的值
时间复杂度\(O(n\log^2n)\)，代码3.2k
[ZJOI2013]K大数查询
你有n个位置，每个位置初始是空的。
一种操作是在a位置到b位置上每个位置插入一个元素c
一种操作是查询a位置到b位置上第k大的数
报告！我会整体二分！不好意思，强制在线。
首要考虑的是内外层的关系：位置和权值哪个作为内层，哪个作为外层？
方案一：外层位置内层权值。
发现操作一是一个区间修改，操作二是一个区间查询。不知道能不能写。
方案二：外层权值内层位置。
发现操作一是一个单点修改，操作二是一个线段树上二分。
所以就线段树套线段树，即线段树上的每一个点都是一棵线段树的根。
时间复杂度\(O(n\log^2n)\)，代码1.5k
[HNOI2016]网络
给你一棵树，支持如下三种操作：
1、在树上插入一条两端点为\(u,v\)，权值为\(w\)的链。
2、删除之前插入的某一条链。
3、查询未经过点\(x\)的链中的权值最大值
可在线。
首先把链剖成\(\logn\)个区间（dfs序上的区间）。
把区间反转，在不在这\(\logn\)个区间范围内的区域做覆盖。
这样就可以查询覆盖了\(x\)点的链中的最大值就可以了。
由于有删除操作所以线段树上的每个节点开一个删除堆。
时间复杂度\(O(n\log^3n)\) 代码3.2k
后记
树状数组套平衡树我没写过，yyb说用来写三维偏序然而三位偏序不是被我树状数组套线段树水过去了吗
总之，大家根据自己的代码风格以及对这些数据结构的熟练程度进行取舍吧
还有对于那些没有强制在线的题目，采用cdq分治或者是整体二分都是不错的选择。
主席树乱讲
主席树乱讲前置技能线段树：动态开点，标记永久化，基本操作离散化介绍主席树即可持久化线段树，也叫作函数式线段树至于为什么叫做主席树，据说是一个叫HJT的神犇在考场上现场yy出来的可持久化线段树：顾名思义就是线... 查看详情
「模板」树套树
「模板」树套树<题目链接>线段树套SBT。有生以来写过的最长代码。虽然能过，但我删除SBT点的时候没回收内存！写了就RE！先放上来吧，回收内存调出来了再修改qwq。#include<algorithm>#include<climits>#include<cstdio>usin... 查看详情
树套树
树套树，顾名思义，就是用一颗树套在另外一组树之上。比方说我们有一颗树，假如它的每一个结点（抽象意义上，一株树由多个结点组成）也是一株树，那么这就形成了树套树。外部树和内部树可以是不同品种的。一般外... 查看详情
树套树初探(代码片段)
最近学了学树套树，做了几道模板题。发现好像有点水咳咳咳。树套树，顾名思义，一个树套一个树。比如树状数组套平衡树，就是把树状数组的每一个结点作为一颗平衡树，线段树套权值线段树，就是一颗线段树，每一个结点... 查看详情
树套树(代码片段)
树套树一种思想，就是一棵树的节点是另一颗树。在外面的叫外层树，在里面的叫内层树。外层树一般是，树状数组，线段树内层树一般是平衡树，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操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过... 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情
洛谷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_ 查看详情