2026 年省选专题系列六：线段树合并与分裂。

线段树合并

把两棵线段树合并成一棵，用于树上问题求解。

应用场景：

  • 树上统计子树信息
  • 合并多个集合的信息
  • 离线处理树上问题

复杂度：总复杂度 O(n log n)。

线段树分裂

把一棵线段树分裂成两棵，用于区间分裂问题。

应用场景：

  • 区间分裂问题
  • 可持久化处理
  • 动态区间操作

经典题型

  • 树上颜色统计
  • 子树众数统计
  • 路径信息合并

学习建议

  • 先掌握动态开点线段树
  • 再学线段树合并
  • 最后学线段树分裂

省选一对一辅导：151 6522 2880