本文目录#
线段树基础#
线段树(Segment Tree)用于区间查询与更新,支持求和、最大值、最小值等操作,复杂度 O(log n)。通过懒惰标记实现区间更新。
结构定义#
1 | class SegmentTree { |
应用场景#
- 区间加减、区间查;
- 动态区间最大值/最小值;
- 线段树 + 离散化用于范围更新;
- 总和、差分结合处理大数据量。
自检清单#
- 是否正确处理懒惰标记的传播?
- 是否使用 long 类型防止溢出?
- 是否对离散化/边界做检查?
参考资料#
- MIT OCW 6.006 Lecture 16 Segment Trees:https://ocw.mit.edu/.../lecture-16-range-queries-segment-trees/
- CP-Algorithms Segment Tree 指南:https://cp-algorithms.com/data_structures/segment_tree.html
- LeetCode 线段树题单:https://leetcode.com/tag/segment-tree/
本作品系原创,采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,转载请注明出处。