线段树合并 笔记

一、二叉树合并

给你两棵二叉树，每棵树的每个节点有点权，现在要合并成一棵二叉树，相同位置的点点权相加，如何操作？

由于这种问题一般有 ${10}^5$ 级别棵树，而总点数很少，所以考虑用和主席树一样的动态开店策略，如下图所示，括号内的是点权，外的是编号。

此处应有图。

接着考虑从根节点开始暴力把 $(a)$ 合并到 $(b)$。

• 从 $1,7$ 开始递归，合并 $1,7$ 的点权。

  • 递归左儿子 $2,8$，合并 $2,8$ 的点权。

    • 递归左儿子 $0,9$，$2$ 没有左儿子，取 $9$，返回。

    • 递归右儿子 $0,0$，均为空，返回。

  • 递归右儿子 $3,10$。

    • 递归左儿子 $4,0$，$10$ 没有左儿子，合并后就有了，$10$ 的左儿子指向 $4$ 返回。

    • 递归右儿子 $0,11$，同 $0,9$ 的情况，返回。

故新树如下所示。

此处应有图。

二、线段树合并

线段树本身也是二叉树，所以可以直接用二叉树合并的方法合并。

三、刷题记录

1. P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

对 $x\to y$ 路径上的 $z$ 货物数量都加 $1$，可以差分为对 $x$ 和 $y$ 的 $z$ 数量加 $1$，在 $\mathrm{lca}(x,y)$ 的父亲处减 $1$，从下往上加即可得到每个节点的 $z$ 数量，而 $\mathrm{lca}(x,y)$ 会被左右两边均算而多算一次，因此这里也要减 $1$。区间问题即被转换为单点问题，于是考虑对每个结点维护一棵线段树，维护各种货物当前的差分信息，并找出其中的最大值，从下往上进行相加的线段树合并即可。

关于空间复杂度：一次操作会至多在 $4$ 棵线段树上增加一条链，总的即为 $O(4m\log v)$，通常而言，开值域的 $2^5$ 倍即可。

2. P3224 [HNOI2012] 永无乡

同样的，考虑对每个连通块维护一棵，即线段树下标表示岛屿的重要程度，值为是否存在 $(0/1)$，并求和。然后就能找到重要程度第 $k$ 小，合并连通块时结合并查集即可。

3. P3521 [POI2011] ROT-Tree Rotations

考虑对每个节点维护一棵权值线段树，同上。由于是先序遍历，故交换前后对回溯以后的答案不影响，只影响当前的 $2$ 棵树内的答案，所以可以直接合并。

合并两棵树时，有逆序对全在左子树，全在右子树，跨越两棵子树的情况。处理第三种并递归左右即可，而第三种显然时 $(p\to \mathrm{ls}\to v)\times (q\to \mathrm{rs}\to v)$（交换前），合并时用两个变量统计交换前后分别的逆序对数，取较小值加入答案即可。