当前位置：首页 > news >正文

线段树的合并：原理、实现与应用

news 2026/7/31 1:07:13

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)。