线段树合并

一句话理解

线段树合并：把两棵权值树合成一棵。

为什么要学

树上启发式、子树颜色种类。

讲解

同位置儿子递归合并，O(log) 均摊到每个点。

例子

像合并两个有序袋。

常见错误

• 每次合并复制导致 n log² 变差。应移动节点。
• 空点没返回另一棵。