现在有两棵线段树，我们的目标是将它们的信息合并成一棵。对于一般的线段树直接遍历然后对应结点合并即可，时间复杂度 \(O(n)\)，那对于动态开点线段树呢？假设我们希望把线段树 \(B\) 的信息合并到 \(A\) 里面，那么从 \(A\) 的根开始遍历，遍历范围是 \(A\) 与 \(B\) 对应位置结点的并。
设当前遍历到 \(u\)，\(u\) 为区间 \([L,R]\) 对应结点。
-
若 \(u\) 在 \(A\) 中有但在 \(B\) 中没有，则返回。
-
若 \(u\) 在 \(B\) 中有但在 \(A\) 中没有，则将 \(B\) 的 \(u\) 子树接到 \(A\) 的对应位置上。
-
若 \(u\) 在 \(A,B\) 中都没有，则返回。
-
若 \(u\) 为叶子，则将 \(B_u\) 的信息并入 \(A_u\)。
-
否则，继续遍历。
上述过程主要方便理解，实现可以做到更加简洁。
这样操作合并若干个线段树的复杂度为 \(n \log V\)，其中 \(n\) 为初始插入的结点数目，\(V\) 为值域。