线段树是省选必考数据结构，本文详解 2026 最新版。
线段树解决什么问题
- 区间求和
- 区间最值
- 区间修改 + 区间查询
线段树核心思想
把区间不断二分，每个节点维护一个区间的信息。
线段树三大操作
1. 建树 build
递归建树，O(n) 复杂度
2. 单点修改 update
递归修改到叶子，O(log n)
3. 区间查询 query
递归查询覆盖区间，O(log n)
懒标记 lazy（关键）
区间修改时不立即更新所有子节点，用懒标记延迟更新。
2026 新增考点
- 线段树合并
- 线段树分裂
- 动态开点线段树
- 可持久化线段树（主席树）
学习建议
- 先掌握基础线段树
- 再学懒标记
- 最后学可持久化
省选一对一辅导：151 6522 2880