合并流程：
需要将 \(u\), \(v\) 所代表的区间 \(l,r\) 进行合并。
如果 \(u\)，\(v\) 至少一个不存在，返回 \(u|v\)。
如果 \(l=r\)，直接把 \(v\) 的信息合并到 \(u\)，并返回 \(u\)。
否则将 \(u\)，\(v\) 左右儿子分别合并为 \(u\) 的儿子，返回 \(u\)。
记得访问儿子前下放标记，结束后更新自己。
时间复杂度为 \(n\log n\)，\(n\log n\) 为初始点数。
证明：
每次合并的花费为 \(k\)，\(k\) 为重合的结点数，合并后会使总点数减少 \(k\)，而总点数非负。
所以复杂度与总点数同阶，为 \(O(n\log n)\)。
一般用于优化有关树的 dp，维护子树信息 的问题。
1.【NOI2020】命运
考虑 dp，设 \(f_{u,i}\) 表示终点在子树 \(u\) 内部的点对，还没有被满足的点对深度最深的恰好为 \(i\) 的方案数。
再讨论 \(u\) 是否选择，\(f_{u,0} = f_{u,0} + \sum_{i\ge 0} f_{u,i}\)。
于是在线段树合并的时候完成 \(v\) 对 \(u\) 的更新，只需线段树维护区间 \(f\) 的和。
从左往右进行合并，合并时维护当前区间 \(l...r\) 的前缀 \(f_{0...l-1}\) 之和即可。
有些问题只对一段区间 \(l...r\) 进行复杂的操作，于是需要把线段树 \(l...r\) 的部分提出，然后再合并回去。
分裂流程：
需要把 \(v\) 中处于 \(x...y\) 的结点分离到 \(u\) 的子树中，当前区间为 \(l...r\)。
若 \([l,r]\in [x,y]\)，把 \(u\) 设为 \(v\)，并把 \(v\) 删除。
否则将 \(u\) 设为新的结点，并将 \(u\) 的左右儿子与 \(v\) 的左右儿子进行分裂。
记得访问儿子前下放标记，结束后更新自己。
1. CF 1515H Phoenix and Bits
and 操作可以用 xor 和 or 实现，因为这三者分别代表取交，取并，取补集。
然后对整个值域建立 线段树/01 Tire。
通过线段树分裂合并提取操作区间。
异或可以用交换左右儿子以及懒标记实现。
或需要将左儿子合并到右儿子处，这个合并的复杂度是均摊的。
额外维护子树内部对于每个二进制位是否存在一个数该位为 \(0\) 或 \(1\)。
如果 \(x\) 的为 \(1\) 的每一位子树内均不同时存在数该位为 \(0\) 或 \(1\)，则给子树进行异或并退出操作。
然后就可以势能分析了。
原文：https://www.cnblogs.com/iqx37f/p/14883218.html