[DS 小计] 线段树合并

引入

现在你有很多棵二叉树。
二叉树的节点总和是 \(n\) 。
现在，你要把它们合并。
怎么做呢？
实际上，写的好是可以 \(O(n)\) 完成的。

前置题目 1

给出 \(2\) 棵二叉树，合并两棵二叉树。

怎么做呢？
很容易的暴力，遍历每个点，合并即可。

合并我们进行以下分类讨论：

• 如果现在 \(u\) ， \(v\) 中任意一左子树/右子树为空，直接接上去即可。
• 否则，递归处理。

这样时间复杂度是重复节点个数。

好像没什么用的样子

前置题目 2

给出 \(n\) 棵二叉树，合并 \(n\) 棵二叉树。节点总数为 \(m\) 。

其实很简单，我们按照上面合并两棵的思路，暴力合并即可。
为什么这样可行呢？时间复杂度不会炸吗？

我们来分析时间复杂度。
那么，我们合并两棵线段树的时间复杂度是确定的。
我们可以理解为，合并后的两个节点，我们删除了其中一个。
也就是说，我们给其中一个打上了标记。
显然，每个节点至多被打上一次标记。
所以时间复杂度是 \(O(m)\) 的。
复杂度的情况保证是不会重复合并两次二叉树。

正题

线段树合并和二叉树合并思想一致。
只是线段树要维护信息。
只需要这样做：
先下方当前节点的标记，然后往下递归合并。
这样我们能保证合并时的两个点没有标记，是正确的。
然后因为你已经下好标记了，然后更新左右子树，子树也是下方好标记/更新了的，直接上传标记(Pushup)即可。

所以，合并时间复杂度是总的点数。
这样就做完了。
具体的，到了叶子节点请特殊处理处理即可。

然后就做完了，完结撒花。