算法

两棵动态开点线段树，直接把一棵线段树上的信息合并到另一棵树上。

递归合并：

• 如果某个节点两棵都有，合并，然后递归下去。

• 否则直接返回节点。

复杂度证明

记权值线段树值域范围为 \(m\)，\(n\) 次插入操作。

因为动态开点，一次插入会新增 \(\log_2 m\) 个节点，总节点数 \(n \times \log_2m\)。

因为一棵直接合并到另一棵，合并时间只和重合节点 \(k\) 有关，只会多递归一层，时间最多 \(3 \times k\)。每次合并一个点就会少一个点，合并 \(n \times \log_2m\) 次节点就全没了，时间复杂度 \(\Theta(n \times \log_2m)\)。合并时候不会申请空间，因此空间复杂度也等于插入时的总节点数 \(\Theta(n\times \log_2m)\)。

例题（咕）