线段树合并是处理“树上信息合并”的神器。别看它名字唬人，代码其实非常短。本文带你手撕模板，并给你 5 道必刷题。
核心思想
我们动态开点建线段树。对于两个线段树节点 x 和 y，如果其中一个为空，直接返回另一个；否则递归合并左右儿子，最后 pushup 更新当前节点信息。
代码模板（以维护区间和为例）：
int merge(int x, int y, int l, int r) {
if (!x || !y) return x + y; // 其中一个为空，返回非空的那个
if (l == r) {
sum[x] += sum[y]; // 叶子节点合并
return x;
}
int mid = (l + r) >> 1;
lc[x] = merge(lc[x], lc[y], l, mid);
rc[x] = merge(rc[x], rc[y], mid+1, r);
sum[x] = sum[lc[x]] + sum[rc[x]];
return x;
}复杂度：合并两棵线段树的复杂度为 两棵树重叠的节点数，总复杂度 O(m log n)。
5 道经典必刷题（按难度排序）
- P4556 [Vani有约会] 雨天的尾巴（入门板子，树上差分 + 线段树合并）
- P3521 [POI2011] ROT-Tree Rotations（逆序对 + 合并时统计贡献）
- P3302 [SDOI2013] 森林（主席树 + 启发式合并进阶）
- CF600E Lomsat gelral（树上众数，经典 DSU on tree 也可做，但线段树合并更优雅）
- P3605 [USACO17JAN] Promotion Counting P（动态开点权值线段树 + DFS 合并）
入土警告：线段树合并极易爆内存，一定要算好节点数量（一般
N * 4不够，动态开点要开到N * (logN) * 2左右）。写完记得检查merge时有没有忘记pushup。
实战小贴士
- 空间估算：对于
n个点，每个点开一条链，总节点数约为n * (⌈log₂n⌉ + 1)，建议开n * 20起步。 - 递归深度：线段树深度约
log n，递归合并时深度可控，一般不会爆栈。 - 返回值：
merge函数一定要返回合并后的根节点编号，否则会丢失信息。