第一次学树套树时，并没有什么特别的感觉，因为属于我的离线分治，我早已遇见
并非第一次学
线段树
- 考虑线段树的本质，即给定序列，能够返回关键字在 \([l,r]\) 内的可加信息之和
- 仅需要保证信息是可加的（如众数，mex 等显然不在此列）
树状数组
- 给定序列，能够返回任意关键字处的前缀和 / 后缀和，需要保证信息是可加的
- 如果要求任意区间内关键字的信息之和，会用到差分，此时还需额外保证信息是可减的（如 min / max 显然不在此列）
主席树 / 可持久化线段树
之前有人在争论『主席树』是否等价于『可持久化线段树』，其实从当前 OI 环境的语境下我觉得是等价的
给定序列，存在关键字 A 和关键字 B，能够求出 \(([0, A'], [B_1, B_2])\) 这个矩形的信息和（这里的矩形可能是 DAG 状的）
也就是说主席树本身存的是关于 A 的信息前缀和
要求 A 只能来源于先前的 A（即 A 具有单调性），且底层信息的 delta 为 1
需要发现这个条件是相当苛刻的，所以这里的 A 通常以时间 / 版本 / DAG 的形式出现
如果信息具有可减性，对于 \(A_2\) 和其某个祖先 \(A_1\)，能够求出 \(([A_1,A_2],[B_1,B_2])\) 这个矩形的信息和。
- 考虑为什么主席树不能解决三维偏序
- 现在已经对关键字 C 排完序了，我们需要求出 \(([0, A], [0, B])\) 这个矩形的信息和
- 发现 A 是不具备单调性的，有没有什么 DS 能够不要求 A 的单调性呢？
树状数组套线段树
- 用 \(n\) 棵线段树维护 B 的偏序关系，用类主席树的方式来排列这些树
发现一次修改需要改一段后缀
这一点我们前面说过了，主席树本身存储的是 A 维的前缀和。
- 所以直接解决这个问题：维护信息的差分。这样就可以通过询问前缀得到原始信息
这个结构和树状数组是很吻合的，考虑在树状数组的每个点上维护动态开点线段树
这样就可以只用修改 log 个线段树
考虑怎么询问
我最初的想法是，做一个线段树合并，利用 DS 本身的树形结构可以有一个 dsu on tree 的复杂度（即 \(O(nq\log^2 n)\)），但显然这个太糖了
正常的做法是，注意到每个点的权值线段树结构相同，所以在 log 个线段树上同时维护，当作包含长度 log 的数组的结构体即可
- 同树状数组，要求信息有可减性
但由于外层的 DS 本质上舍弃了主席树 DAG 的结构
导致不能直接简单用于树上问题，而是需要在 DFS 序上作文章
实际上常数很大，超过 \(10^5\) 就不太能跑得动了
Dynamic Rankings / K大数查询
https://www.luogu.com.cn/problem/P2617 / https://www.luogu.com.cn/problem/P3332
- 全局第 \(k\) 大就是普通的权值线段树上二分，抑或平衡树，抑或 01-Trie（三者等价）
- 这里的权值线段树上二分，其实是矩形第二维限制的变体
- 发现这里只需要简单地维护元素个数，是具有可减性的。
三维偏序（陌上花开）
https://www.luogu.com.cn/problem/P3810
- 树状数组套权值线段树即可
二逼平衡树
- 和 k 大数差不多，都是权值线段树那些东西
网络管理
https://www.luogu.com.cn/problem/P4175
维护带修树上简单路径第 \(k\) 大。
- 做树上差分即可转化为序列第 \(k\) 大。
买宝石
http://222.180.160.110:61235/contest/6620/problem/4
给定根为 \(1\) 的树，每个点 \(u\) 上有 \(k_u\) 个价钱为 \(w_u\) 的物品，可以在时间 \(t_u\) 及之后获得
给定 \(Q\) 次询问，从问 \(x\) 出发到根的路径上所有在时刻 \(T\) 可以获得的物品全部拿出来排成一列，拥有 \(K\) 金钱时，按照价值从小到大购买，买到的最后一个物品价值。
\(n\le 10^5\)，价钱：\(10^{15}\)，时间：\(10^5\)，个数：\(10^5\)。
- 信息自带一个有序的时间偏序维 \(T\) 且原生有序，所以不能整体二分，必须处理 \(k\) 偏序维和 \(w\) 二分维。
- 总的来说，就是维护了两个关键字，或者说一个矩形
- 根据在 A，B 维需要做的操作选择，以及需要维护的信息类型，选择相应的数据结构
关于整体二分
- 考虑动态区间第 K 大这一类的问题，特征是 A 维『求和』，B 维二分
- 此时可以把对 B 维的二分提到外层一起进行，反过来对 A 维应用数据结构
- 考虑到树套树常数过大，所以在能用整体二分的时候不推荐用树套树