精选文章

📚 精选阅读

1. LeetCode 303 - 区域和检索 - 数组不可变

   • 难度：简单

     线段树入门

   • 链接：https://leetcode.cn/problems/range-sum-query-immutable/
2. LeetCode 307 - 区域和检索 - 数组可修改

   • 难度：中等

     单点更新线段树

   • 链接：https://leetcode.cn/problems/range-sum-query-mutable/
3. LeetCode 729 - 我的日程安排表 I

   • 难度：中等

     线段树基础应用

   • 链接：https://leetcode.cn/problems/my-calendar-i/
4. LeetCode 731 - 我的日程安排表 II

   • 难度：困难

     懒更新线段树

   • 链接：https://leetcode.cn/problems/my-calendar-ii/
5. 《线段树详解》 — 算法导论级别
   • 图解清晰，附完整代码
   • 推荐：OI Wiki

🔧 实战路径

第一阶段：基础线段树
├─ LeetCode 303：区间求和（不可变）
├─ LeetCode 307：单点更新 + 区间查询
└─ 理解 tree[] 和 build 过程

第二阶段：懒更新
├─ LeetCode 731：日程重叠问题
├─ 理解 lazy[] 标记的作用
└─ 理解 _push_down 何时调用

第三阶段：综合应用
├─ 区间赋值 vs 区间加法
├─ 区间最大值 / 最小值
└─ 区间染色问题

📖 推荐学习顺序

1. 理解线段树的结构 → 画一棵具体的树
2. 理解 build 过程 → 自底向上汇总
3. 理解 query 过程 → 区间完全包含 / 完全不包含 / 部分重叠
4. 理解单点 update → 自底向上更新
5. 理解懒更新 → 延迟传递 + _push_down

💡 面试常考点

面试高频问题：

1. 线段树的空间复杂度为什么是 4n？
2. 懒更新标记的作用是什么？
3. 线段树和树状数组的区别？

相关阅读：线段树（Segment Tree）详解