核心概述
区间容器用于维护区间集合并支持插入、删除、相交与覆盖等查询，常以有序集合、区间树或并查集合并等结构实现以在对数时间内完成操作。
原文引述
Description: Container for intervals [l,r) with fast insertion, deletion, overlap queries, and union operations. Implemented via interval tree, ordered set, or DSU with merging.（摘自本节点现有英文注释） Time: Insert/delete O(log n); overlap query O(log n) or O(k) for k overlaps（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）
展开阐述
-
定义与背景
- 维护一组半开区间 [l, r)，要求高效支持区间级的增删与查询；常见于时间安排冲突检测、扫描线活跃集、以及按区间的动态维护问题。
- 典型抽象包含：插入/删除某区间、查询与给定区间/点相交的集合、合并重叠区间、计算覆盖关系等。
-
接口/数据结构与输入输出语义
- 有序集合（std::set<pair<l,r>>）：按左端点排序，便于用 lower_bound 定位候选，适合规模中等的离线/在线维护。
- 区间树/线段树：节点维护覆盖区间与辅助信息（如最大右端点、最优值），支持区间更新/查询。
- 并查集式区间合并：将相邻或相交区间归并为连通块，维护每个集合的最小左端点与最大右端点。
- 输入输出约定：区间统一采用左闭右开 [l, r) 表示；查询返回与目标相交的所有区间或相应统计量。
-
核心流程与关键要点
- 基于 set 的相交枚举：
- 使用 lower_bound({x, -∞}) 找到第一个可能相交的候选，向后扫描直至左端点 ≥ 查询右端点。
- 插入/删除为 O(log n)，相交枚举为 O(k)（与相交数目有关）。
- 基于区间树的相交查询：
- 节点存储区间与子树最大右端点；查询时利用最大右端点剪枝，仅访问潜在相交的分支。
- 合并操作：
- 批量合并可先将所有区间按左端点排序，再线性扫描合并重叠段，或在 set 插入时向前/向后合并相邻可并区间。
- 一致性与边界：
- 保持半开约定，避免端点相等时的歧义；删除需与插入时的键一致。
- 基于 set 的相交枚举：
-
复杂度与边界条件
- set：单次插入/删除 O(log n)；相交查询 O(log n + k)。
- 区间树：构建 O(n)，单次更新/查询 O(log n) 或依赖覆盖分布。
- 大量区间时，专用区间树更稳定；仅需维护并集时，用排序+线扫更简洁。
-
常见变体/扩展
- 加权区间容器：在节点上维护权值、最优值等，以支持按覆盖代价的聚合查询。
- 动态区间覆盖：与线段树结合，进行区间加/减及覆盖统计。
- 与并查集整合：按相交关系连通并维护每个集合的 [minL, maxR)。
-
注意事项
- 插入前可与相邻区间尝试合并减少碎片；删除时注意仅删除完全匹配的键。
- 大量删除场景可采用延迟删除并周期性清理，降低常数开销。