应自实现带max_end缓存的二叉搜索树，因sortedcontainers的IntervalTree实为线性扫描，插入和查询均为O(n)；标准区间树需以start排序，每个节点存max_end用于剪枝，旋转时须同步更新，overlap_search需严格按重叠条件与剪枝逻辑递归。
为什么不用 sortedcontainers 自带的 IntervalTree
因为它的 IntervalTree 实际上是基于 SortedSet 的线性扫描变种，插入 O(n)，查询重叠仍是 O(n) —— 它根本不是计算几何意义上的区间树（interval tree），只是个带区间语义的有序容器。真要支持 O(log n) 重叠查询，得自己实现带“最大端点”缓存的二叉搜索树。
核心结构：每个节点必须存 max_end
标准区间树的关键是每个节点额外维护子树中所有区间的右端点最大值（max_end）。它不参与排序，只用于剪枝：若当前节点的 max_end 小于查询区间左端点，整棵右子树可跳过。
实操建议：
- 节点类至少包含
start、end、max_end、left、right字段；max_end在每次插入/旋转后必须自底向上更新 - 排序依据只能是
start（左端点），不能用区间中点或长度，否则无法保证 BST 性质 - 插入后若做 AVL 或红黑平衡，旋转时别忘了同步更新
max_end—— 这是最容易漏的点，会导致后续查询漏匹配
overlap_search 的递归逻辑怎么写才不漏不重
查重叠不是查包含，只要 query_start < node.end and query_end > node.start 就算重叠。但关键在剪枝条件：
立即学习“Python免费学习笔记（深入）”；
实操建议：
- 先检查当前节点是否重叠，是则加入结果（注意：不能立即 return，因为左右子树可能还有）
- 若
node.left.max_end >= query_start，才递归进左子树（左子树里可能有右端点够大的区间，能跨过 query_start） - 若
node.right and node.right.start < query_end，才递归进右子树（右子树左端点太靠右就不可能重叠） - 不要用
node.left.max_end > query_end剪枝——这是常见错误，会漏掉[1,10]查询[5,6]时左子树中[3,7]这种情况
性能陷阱：Python 中真正卡慢的地方在哪
纯 Python 实现的区间树，90% 的开销不在算法逻辑，而在对象创建和属性访问。比如每层递归都新建列表存结果、频繁调用 getattr 访问 max_end，都会让 O(log n) 理论优势被吞噬。
实操建议：
- 把结果收集从“返回新列表”改为传入预分配的
list参数（results.append(...)） - 所有节点字段用
__slots__ = ('start', 'end', 'max_end', 'left', 'right')，省去__dict__开销 - 避免在递归中做区间对象构造（如
Interval(start, end)），直接存元组或原始数值 - 如果数据量稳定超 10⁵ 且对延迟敏感，别硬刚纯 Python —— 改用
cython绑定或直接调boost::icl的 C++ 库更实际
真正难的不是写对逻辑，而是让 max_end 更新、剪枝条件、递归出口三者严丝合缝；错一处，要么漏结果，要么退化成 O(n)。
