本文首发于 CSDN

配套代码仓库：Python_exercise_19

适用人群：有一定 Python 基础、想深入理解递归与数据结构的开发者

---

📌 写在前面

很多人在学习线段树时会遇到两个坎：一是看不懂递归，二是看得懂但写不出来。

为了帮你跨过这两道坎，我设计了这组 “递归三部曲”​ 练习题，围绕一个真实的 IoT 场景——鸿蒙网关乱序数据采集与实时告警​ 展开。

• 第 20 题：让你亲手用手画递归的每一步（二分查找、区间分裂、线段树更新与查询），建立直觉。

• 第 21 题：要求你把手工模拟的过程翻译成代码（静态查询→动态更新→顺序滑动窗口），实现“学以致用”。

• 第 19 题：将线段树嵌入乱序数据流的真实工程场景，完成从理论到实践的飞跃。

三题环环相扣，核心思想只有一个——递归。

如果你曾被递归折磨过，这组题就是最好的“康复训练”。

---

🧩 题目总览

编号	题目名称	领域	核心知识点	难度（华为OD）	难度（LeetCode）	角色
19	鸿蒙IoT网关数据采集与实时告警​	数据结构·算法	动态开点线段树、区间最大值查询、乱序数据流、滑动窗口	⭐⭐⭐（中等偏上）	Medium	主任务​
20	扩展练习（PyE19 补漏）​	手工模拟·代码填空	二分查找手工模拟、区间分裂、线段树更新与查询手工模拟、边界条件处理、暴力法对比、代码填空	⭐⭐（简单~中等）	Easy-Medium	辅助理解
21	扩展练习（PyE19-2 补漏）​	基础实现·顺序窗口	静态线段树查询、动态线段树更新、顺序滑动窗口最大值、复杂度对比	⭐⭐⭐（中等）	Easy-Medium	辅助理解

难度说明：参照华为 OD 机试和 LeetCode 体系，侧重数据结构与算法实现。

---

🎯 三大亮点：为什么这组题值得刷？

亮点一：递归思想贯穿始终，三步彻底搞懂

阶段	题目	做什么	收获
第一步：用手画​	第20题	手工模拟二分查找、区间分裂、线段树更新与查询的每一步递归调用	建立“分治”的肌肉记忆，再也不怕递归
第二步：用代码写​	第21题	将手工模拟转化为递归函数，实现动态开点线段树，并应用于顺序滑动窗口	理解递归如何自然地创建节点、回溯更新
第三步：用工程练​	第19题	在线段树基础上处理乱序数据流，实现实时滑动窗口最大值	掌握递归在真实场景中的应用，应对面试高频题

亮点二：手工模拟 → 代码填空 → 独立实现，层层递进

• 第20题​ 分为七阶，从“用手画”到“代码填空”，再到“独立实现”，确保你真正理解每一行代码背后的物理意义。

• 第21题​ 在20题的基础上，要求你从零写出线段树，并立即应用到顺序滑动窗口问题，实现“学以致用”。

• 第19题​ 将线段树嵌入真实 IoT 场景，处理乱序数据、窗口滑动、重复时间戳、负值等边界，完成从理论到实践的飞跃。

亮点三：边界条件与性能优化并重

• 第20题第四阶专门设置了边界条件手工计算（重复时间戳、负值、空窗口），防止你在代码中被动踩坑。

• 第21题第四阶要求你进行复杂度对比，理解“为什么需要线段树”以及“什么时候暴力法更快”。

• 第19题的评分要点明确指出：不仅要正确，还要高效（O(1) 均摊的单调队列解法可作为进阶挑战）。

---

👥 适合谁学？

• ✅ 已经掌握基础 Python 语法，希望深入学习数据结构的开发者

• ✅ 正在准备华为 OD 机试或大厂面试的求职者（线段树和滑动窗口是高频考点）

• ✅ 对递归感到困惑，想通过“手工模拟+代码”彻底搞懂的学习者

• ✅ 希望理解“从暴力到优化”思维过程的工程师

---

🚀 学习路线建议

1. 先做第 20 题的手工模拟：拿出纸笔，严格按照题目要求画出每一步的 left、right、mid，画出区间分裂树，画出线段树更新后的节点值变化。这一步至关重要，它是后续所有代码的基础。

2. 完成第 20 题的代码填空与暴力实现：填空能帮你检验对代码结构的记忆，暴力实现则让你亲身体会“为什么需要优化”。

3. 进入第 21 题：先实现静态线段树查询（21-1），再扩展为动态更新（21-2），然后封装成顺序滑动窗口类（21-3），最后进行复杂度对比（21-4）。

4. 挑战第 19 题：在 21-3 的基础上，增加乱序处理逻辑（未来数据不可见）。你可以先用暴力法验证正确性，再尝试用线段树优化。

5. 进阶思考：线段树查询是 O(log N)，但第 19 题其实可以用单调队列做到 O(1) 均摊。如果你有兴趣，可以尝试实现单调队列解法，并对比两种方案的优劣。

---

📁 文件结构

.
├── README.md                                    # 本文档
├── 19_harmony_iot_gateway.py                    # 鸿蒙IoT网关数据采集与实时告警（主任务）
├── 20_extend_exercise_pye19.py                  # 扩展练习（PyE19 补漏）
│   ├── 第一阶：二分查找手工模拟
│   ├── 第二阶：区间分裂与区间树
│   ├── 第三阶：线段树更新与查询手工模拟
│   ├── 第四阶：边界条件手工计算
│   ├── 第五阶：暴力实现与复杂度对比
│   ├── 第六阶：代码填空
│   └── 第七阶：独立实现
└── 21_extend_exercise_pye19_2.py                # 扩展练习（PyE19-2 补漏）
    ├── 21-1：静态线段树查询
    ├── 21-2：动态线段树更新
    ├── 21-3：顺序滑动窗口最大值
    └── 21-4：复杂度对比与思考

---

💬 写在最后

这三道题是我精心设计的“递归三部曲”，希望能帮你彻底征服线段树和滑动窗口这两个高频考点。如果你在练习过程中有任何疑问，或者发现了更好的实现方式，欢迎在评论区留言交流！

觉得有用的话，点个赞 👍 再走吧～

---

📜 许可

本项目仅供学习交流使用，遵循 MIT License。