如何基于Interval Tree变体实现对数时间的区间包含查询？

嘿，这个问题我之前处理过类似场景，完全不用暴力遍历，咱们可以通过拆解查询条件+预处理合适的数据结构来实现对数级别的查询效率，完美适配1e5次查询的需求。

核心思路：把“包含”条件拆成两个可查询的维度 #

要找完全落在查询区间[Ql, Qr]里的区间[Il, Ir]，本质就是要满足两个条件：

• 区间的左端点Il ≥ Ql
• 区间的右端点Ir ≤ Qr

我们可以把这两个条件拆解，通过预处理让每个条件的筛选都能快速完成，最后组合结果就行。

具体实现方案 #

我给你两个常用的方案，一个适配离线/在线场景，一个是离线场景下的高效优化，你可以根据需求选择：

方案1：排序+归并树（离线/在线通用，查询O(log²N)） #

预处理步骤

1. 按右端点排序区间：把所有原始区间按Ir从小到大排序，得到sorted_intervals。比如你给的例子，排序后是[(1,3), (0,4), (2,5), (2,6)]。
2. 构建归并树：基于排序后的区间左端点数组L（例子里是[1,0,2,2]）构建归并树。归并树是一种特殊的线段树，每个节点存储对应区间内L元素的有序列表，这样我们可以快速查询任意前缀区间里满足Il ≥ Ql的元素数量。

查询步骤

对于每个查询[Ql, Qr]：

1. 用二分查找在排序后的右端点数组R（例子里是[3,4,5,6]）中找到最大的索引k，使得R[k] ≤ Qr——这一步筛选出所有右端点符合要求的区间。
2. 在归并树中查询前k+1个左端点里，Il ≥ Ql的数量——这一步用二分查找在归并树的节点有序列表中找下界，统计数量即可。

拿你的例子验证：查询[1,5]时，第一步找到k=2（因为R[2]=5 ≤5），第二步在归并树的前3个左端点的有序列表[0,1,2]中，找≥1的下界是索引1，数量是3-1=2，完全正确。

方案2：坐标压缩+ Fenwick Tree（离线专属，查询O(logN)） #

如果所有查询是提前已知的，这个方案的查询效率会更高：

预处理步骤

1. 坐标压缩：收集所有区间的左端点Il、所有查询的Ql和Qr，把这些数值映射到连续的整数索引（解决数值范围过大导致无法直接用数组存储的问题）。
2. 排序区间和查询：把区间按Ir升序排序，把查询按Qr升序排序，同时记录每个查询的原始索引（方便最后把结果对应到原查询顺序）。
3. 初始化Fenwick Tree：这是一种能快速统计前缀和的数据结构，用来记录左端点的出现次数。

查询步骤

1. 遍历排序后的查询，对于当前查询的Qr，先把所有Ir ≤ Qr的区间的Il插入到Fenwick Tree中（对应索引位置计数+1）。
2. 查询Fenwick Tree中Il ≥ Ql的数量：用总插入数减去Il < Ql的前缀和即可。
3. 最后把结果按查询的原始索引排序，得到每个查询的答案。

还是用你的例子：排序后的查询[1,5]的Qr=5，先插入Ir≤5的三个区间的Il（1、0、2），然后查询Il≥1的数量：总插入数3减去Il<1的数量（只有0，计数1），得到3-1=2，正确。

为什么这两个方案比暴力好？ #

暴力解法每次查询要遍历所有N个区间，时间复杂度是O(Q*N)，当Q和N都是1e5时，就是1e10次操作，完全跑不完。而上面的方案，预处理时间是O(NlogN)，查询时间是O(QlogN)或者O(Qlog²N)，1e5次查询最多也就4e7次操作，完全能轻松处理。

额外补充：动态区间场景 #

如果你的场景需要动态添加区间（不是静态预处理所有区间），可以用平衡二叉搜索树（比如C++的std::set）维护按Ir排序的区间，同时用std::multiset维护对应的Il。插入区间是O(logN)，查询时：

1. 用set::upper_bound找到所有Ir ≤ Qr的区间。
2. 用multiset::lower_bound统计这些区间中Il ≥ Ql的数量。
   这样每次查询也是O(logN)，完全满足需求。

内容的提问来源于stack exchange，提问作者cracra