1. 引言

线段树（Segment Tree）是一种用于高效处理区间查询与更新的数据结构。在解决某些复杂问题时，我们可能需要维护多棵线段树，并动态地将它们合并。线段树的合并（Segment Tree Merging）正是这样一种操作，它可以将两棵线段树的信息融合到一棵树中，是处理树上问题（如树上启发式合并）和离线查询的有力工具。

本文将深入探讨线段树合并的原理、实现细节，并通过具体例题展示其应用场景。

2. 线段树合并的原理

2.1 基本思想

线段树合并的核心思想是：同时遍历两棵线段树（它们维护的区间范围必须相同），递归地将对应节点的信息合并。如果某个节点在一棵树中为空，则直接返回另一棵树的对应节点作为合并结果。

这种合并方式通常是“可持久化”的，即不破坏原有的树结构，而是创建新的节点来存储合并后的信息，从而支持回溯或并行维护多个版本。

2.2 适用条件

• 动态开点线段树：由于合并过程中可能需要创建新节点，通常使用动态开点（即不预先建立完整二叉树，而是按需创建节点）的方式实现线段树。
• 信息可加性：线段树节点维护的信息（如区间和、最大值、出现次数等）必须支持合并操作。例如，对于区间和，合并就是将两个节点的值相加。

3. 实现细节

3.1 数据结构定义

以下是一个典型的动态开点线段树节点定义（以维护区间和为例）：

struct Node { int l, r; // 左右子节点的指针（在数组中的下标） long long sum; // 节点维护的信息（此处为区间和） // 可根据需要添加其他信息，如 lazy 标记、最大值等 } tr[MAXN * 40]; // 预留足够空间，通常为 O(n log n) 级别 int root[MAXN]; // 每棵线段树的根节点指针 int idx = 0; // 动态开点计数器

3.2 合并函数

合并函数merge(int p, int q, int l, int r)是关键，其中p和q分别是两棵待合并线段树在当前区间的节点指针，[l, r]是当前区间。

int merge(int p, int q, int l, int r) { if (!p || !q) return p | q; // 一方为空，直接返回另一方 if (l == r) { // 到达叶子节点，合并信息（例如求和） tr[p].sum += tr[q].sum; // 注意：这里复用了 p 节点，也可以创建新节点 return p; } int mid = (l + r) >> 1; tr[p].l = merge(tr[p].l, tr[q].l, l, mid); tr[p].r = merge(tr[p].r, tr[q].r, mid + 1, r); // 向上更新信息 pushup(p); return p; }

注意：上述实现是“破坏性”合并，即合并后树q的节点可能被丢弃或复用。若需要可持久化（保留原树），则应在合并时创建新节点。

3.3 可持久化合并

只需稍作修改，在递归合并前创建新节点即可实现可持久化合并：

int merge(int p, int q, int l, int r) { if (!p || !q) return p | q; int u = ++idx; // 创建新节点 if (l == r) { tr[u].sum = tr[p].sum + tr[q].sum; return u; } int mid = (l + r) >> 1; tr[u].l = merge(tr[p].l, tr[q].l, l, mid); tr[u].r = merge(tr[p].r, tr[q].r, mid + 1, r); pushup(u); return u; }

4. 时间复杂度分析

线段树合并的时间复杂度与两棵树重合的节点数成正比。在最坏情况下，如果两棵都是满二叉树，复杂度为 O(n)。但实际应用中，由于动态开点，许多节点为空，合并的均摊时间复杂度往往接近 O(m log n)，其中 m 是插入操作的数量。可以证明，进行 n 次插入和合并的总时间复杂度为 O(n log n)。

5. 应用场景与例题

5.1 树上启发式合并（DSU on Tree）

在解决子树统计问题时，可以为每个节点建立一棵权值线段树，维护其子树内颜色的出现次数。在 DFS 回溯时，将子节点的线段树合并到当前节点，并利用启发式规则（合并到大小更大的树上）来保证复杂度。

例题：CF 600E Lomsat gelral。求每个子树中出现次数最多的颜色（可能多个）的编号和。

5.2 可持久化线段树合并

用于处理离线查询，尤其是涉及树形结构上路径或子树的问题。通过可持久化合并，可以在保留历史版本的同时进行查询。

例题：洛谷 P4556 [Vani有约会]雨天的尾巴。在树上进行路径加操作，最后询问每个节点上数量最多的救济粮种类。

5.3 区间排序与维护

有些问题需要维护若干个有序序列，并支持合并操作。可以用线段树（或权值线段树）来模拟这些序列，合并操作即对应线段树的合并。

6. 总结

线段树合并是一种强大而灵活的技巧，它将线段树的应用从单一序列扩展到了树形结构和动态集合的领域。掌握其原理和实现，能够为解决一系列复杂的区间统计和树上问题提供清晰的思路。关键点在于理解动态开点、信息合并的方式以及时间复杂度的均摊分析。

在实际编码中，需要注意内存管理（数组大小）和合并时信息更新的正确性。建议从经典例题入手，逐步体会其精妙之处。