线段树合并¶

线段树合并是一种广泛运用的科技，是近年来的热门考点。

线段树合并，顾名思义，就是合并两棵线段树。线段树合并的基本做法可以参照雨天的尾巴，在此不做赘述。

一些性质¶

在此简要提及线段树合并的一些要点。

线段树合并主要用于求解树上问题。
线段树合并只能够合并动态开点线段树。
线段树合并中，普通线段树只支持单点修改。将线段树标记永久化后，可以进行区间修改。

复杂度证明¶

约定，线段树的下标范围为 $N$ ，修改次数为 $M$ 。

线段树合并的空间复杂度为 $O(M\log N)$ 。因为对于空树的单次修改，总会增加 $O(\log N)$ 个节点；对于非空树的单次修改，至多会增加 $O(\log N)$ 个节点。

线段树合并的空间复杂度为 $O(M\log N)$ 。因为在一次合并操作后，产生的新树总是相比比原先两棵树被删去了一些节点；这些被删去的节点每个节点会贡献 $O(1)$ 的时间复杂度，整个合并过程至多删除了 $O(M\log N)$ 个节点，故时间复杂度为 $O(M\log N)$ 。

技巧¶

处理树上问题时，有一种广泛使用将空间降至 $O(N)$ 的 trick，即垃圾回收。每次合并会删除一些节点，用一个数组将这些废弃的空间存储下来，在创建新节点时优先使用这些废弃空间。

遗憾的是，这种做法是错误的，空间复杂度仍为 $O(M\log N)$ 。考虑下图：

自然地，我们可以考虑优先搜索重儿子。这样空间复杂度应该在 $O(N)$ 左右。

线段树合并还可以处理 01 Trie、优化树形 DP。具体做法请看下面的例题。

例题选做¶

联合省选 2020 树 ¶

给你一颗 $n$ 个节点的有根树 $T$ ，每个点都有一个权值 $v_i$ 。定义 $d(i,j)$ 为 $i$ 到 $j$ 的距离， $val_i=\bigoplus\limits_{j\in tree_i}(v_j+d(i,j))$ ，求 $\sum\limits_{i=1}^nval_i$ 。

题解

考虑 $val_i$ 与 $val_j$ （ $j\in son_i$ ）的关系。

设 $s_i$ 表示 $v_j+d(i,j)$ （ $j\in tree_i$ ），则 $s_i=\left(\bigcup\limits_{j\in son_i}\bigcup\limits_{k\in s_j}\{k+1\}\right)\bigcup\{v_i\}$ 。在这个过程中，所有儿子中的元素只增加了 $1$ 。

全局加 $1$ 可以方便地用 01 Trie 维护，而 01 Trie 和动态开点线段树具有相同的性质，于是并集操作可以仿照线段树合并来合并 01 Trie。

NOI2020 命运 ¶

给定有根树上若干组点对 $(u,v)$ ，且 $u$ 是 $v$ 的祖先。给每条边 01 染色，求保证每组 $u,v$ 之间路径上都存在至少一条 1 边的方案数。

题解

设 $dp_{i,j}$ 表示以在 $i$ 的子树中，所有未被覆盖的点对中 $u$ 的深度最大值为 $j$ 时的方案数。则新加入一棵子树 $v$ 时，有：

$dp^\prime_{i,j}=dp_{i,j}\cdot\sum\limits_{k=0}^{dep_i}dp_{v,k}+dp_{i,j}\cdot\sum\limits_{k=0}^jdp_{v,k}+dp_{v,j}\cdot \sum\limits_{k=0}^{j-1}dp_{i,k}$

直接转移复杂度是 $O(n^2)$ 的。考虑用线段树存储 $dp$ 数组。合并时， $\sum\limits_{k=0}^{dep_i}dp_{v,k}$ 可以事先查出；前缀和也可以在下推前查询左子树。于是该题用线段树合并解决了。