线段树合并/分裂
算法简介
一种快速合并、分裂线段树(一般为权值线段树)的算法，时空间复杂度 $O(m\log n)$。
算法思想
更新、分裂线段树时动态开点，易知更新操作时空间复杂度 $O(\log n)$。
关于分裂操作，遇到空结点则返回。其余操作同线段树查询，遇到分裂区间的子区间则将原节点转移给新节点，然后返回。
所以分裂操作的时空间复杂度同线段树查询操作的时间复杂度，即 $O(\log n)$。
关于合并操作，如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
关于合并操作的时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，而每次合并一个节点等价于删除一个节点。
每个节点至多被删除一次，所以合并操作的总时间复杂度等于空间复杂度，即 $O(m\log n)$。
代码模板
算法练习
习题一
题意
给定一棵 $n$ 个节点的数，$m$ 个操作。
每个操作三个参数 $x,y,z$，表示给结点 $x$ 到 $y$ 的树链上的每个点打上一个 $z$ 号标记。
经过所有操作后输出每个结点被打上的最多的标记的编号(满足条件的标记存在多个时输出编号最小的)，如果该结点未被标记过，输出 $0$。
题解 1
离散化处理标记编号，防止 $\text{MLE}$。
每个结点用一棵权值线段树维护该结点的所有标记状态，树上差分打标记，最后从叶子结点开始向上合并即可。
题解 2
考虑树剖，将树上问题转换为区间问题，更新路径时只打差分打标记。
最后询问时只建一棵权值线段树，依次释放区间上每个位置的标记，维护标记前缀和、答案。
时间复杂度 $O(m\log^2 n)$，空间复杂度 $O(m\log n)$，但常数远小于线段树合并。
习题二
题意
给定 $n$ 个点，所有点的点权恰好为 $1 \sim n$ 的排列，接下来两种操作。
- 询问与某点 $x$ 联通的点集中的第 $k$ 大元素的编号，若不存在输出 $-1$。
- 连接点 $u$、$v$。
题解
每个点维护一棵权值线段树，并查集维护连通分量。
对操作 $1$ 类似名次树操作，对操作 $2$ 使用线段树合并即可，时空间复杂度 $O(n\log n)$。
习题三
题意
一棵 $n$ 个结点的树，树上有 $m$ 个玩家，第 $i$ 个玩家的起点为 $s_i$，终点为 $t_i$，每个玩家每秒移动一条边。
在每个结点放置一名观察者，第 $i$ 个结点的观察者会在第 $w_i$ 秒观察到达该点的玩家。
玩家到终点后立即消失，但可以在该时刻被观察者观测。
问每个观察者观察到的玩家数量。
题解 1
先将树转化为一棵有根树，考虑玩家对的结点 $u$ 的观察者的贡献。
可以把玩家的运动分解为 $s\to \text{LCA}(s,t)\to t$。
考虑 $s\to \text{LCA}(s,t)$，只当且仅当 $u\in \{s\to \text{LCA}(s,t)\}$ 且 $w_u=d_s-d_u$ 才产生贡献。
考虑 $\text{LCA}(s,t)\to t$，只当且仅当 $u\in \{\text{LCA}(s,t)\to t\}$ 且 $\text{dist}(s,t)-w_u=d_t-d_u$ 才产生贡献。
分离变量，得 $w_u+d_u=d_s$ 和 $w_u-d_u=\text{dist}(s,t)-d_t$，可以考虑每个结点用两个桶维护可以产生贡献的 $d_s$ 和 $\text{dist}(s,t)-d_t$ 的数量。
然后考虑怎么处理 $u\in \{s\to \text{LCA}(s,t)\}$ 和 $u\in \{\text{LCA}(s,t)\to t\}$ 这两个限制条件。
考虑树上差分，在 $s$ 和 $t$ 结点打上增加标记， $\text{LCA}(s,t)$ 结点打上删除标记。
对每个结点，先 $\text{dfs}$ 子节点，然后处理增加标记，然后查询答案，最后处理删除标记。
考虑如果 $\text{LCA}(s,t)$ 满足 $w_{\text{LCA}(s,t)}+d_{\text{LCA}(s,t)}=d_s$，必有 $w_{\text{LCA}(s,t)}-d_{\text{LCA}(s,t)}=\text{dist}(s,t)-d_t$，导致 $s$ 和 $t$ 重复贡献，所以要提前处理。
题解 2
树上差分的思路同题解 1，但这次考虑用线段树代替桶维护答案，对每个点可以直接处理贡献，然后从叶子结点向上合并线段树即可。
贴了一段别人的代码。
