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