区间树算法

题目描述：设计一个数据结构，能够高效地存储和查询区间集合。支持两种操作：添加一个新区间，以及查询与给定区间重叠的所有区间。

解题过程：

1. 问题分析

   • 我们需要维护一个动态区间集合，支持快速插入和重叠查询
   • 朴素解法是存储所有区间，查询时遍历所有区间检查重叠，时间复杂度为O(n)
   • 我们需要更高效的数据结构，目标是将查询时间优化到O(logn + k)，其中k是结果数量

2. 数据结构设计

   • 使用平衡二叉搜索树（通常用红黑树或AVL树）
   • 每个节点存储一个区间[l, r]和该节点为根的子树中所有区间的最大右端点max_end
   • max_end用于在搜索时快速判断是否需要进入子树

3. 关键属性：max_end

   • 对于节点x，max_end = max(x.interval.r, x.left.max_end, x.right.max_end)
   • 这个属性让我们能够提前判断：如果当前节点的max_end < 查询区间的左端点，说明整个子树都没有重叠区间

4. 重叠查询算法

   函数query(node, query_interval, results):
     如果node为空，返回
   
     如果当前节点的区间与query_interval重叠：
        将当前节点区间加入results
   
     如果左子树非空且左子树的max_end ≥ query_interval.l：
        递归查询左子树
   
     如果右子树非空且node.interval.l ≤ query_interval.r：
        递归查询右子树
   

5. 插入操作

   • 按照区间左端点作为键值进行标准BST插入
   • 插入后更新路径上所有节点的max_end属性
   • 由于使用平衡BST，插入后可能需要进行旋转操作，旋转时需要重新计算max_end

6. 复杂度分析

   • 插入：O(logn)，需要更新路径上的max_end
   • 查询：O(logn + k)，k是结果数量
   • 空间：O(n)

7. 实际应用

   • 数据库系统中的区间查询
   • 日历应用中的时间区间冲突检测
   • 基因组学中的基因位置查询

这个算法的核心思想是通过max_end属性来剪枝，避免不必要的子树遍历，从而保证查询效率。