跳到主要内容

线段树合并 & 分裂

参考资料​

简介​

在动态开点的权值线段树上，线段树合并 把两棵树对应位置的节点递归合并成一棵：某一侧为空时直接返回另一侧，否则递归合并左右子树并上传。

合并的总复杂度与被合并掉的节点数同阶，因此把 nn 棵单点线段树两两合并的总代价为 O(nlog⁡n)O(n\log n)。配合 线段树分裂（按排名或值域拆出一棵子树）可支持更灵活的操作，常与树上差分结合处理路径加、子树查询等离线问题。

例题​

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

村落里一共有 nn 座房屋，并形成一个树状结构。然后救济粮分 mm 次发放，每次选择两个房屋 (x,y)(x, y)，然后对于 xx 到 yy 的路径上（含 xx 和 yy）每座房子里发放一袋 zz 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。