如何高效筛选数组中满足from<x且to>x的元素

你之前用两个排序列表求交的方案，核心瓶颈在于当查询点x落在整个数值范围的中间段时，from <x和to >x对应的两个候选集都会接近全量数据规模，跨集合求交的遍历开销会把二分查找的优势完全吃掉。结合你接受一次性初始化开销的前提，可以换用下面几种成熟的静态索引方案，完全绕开大集合求交的环节。

最优性能方案：区间树索引 #

区间树就是专门为「查找所有覆盖指定点的区间」这类场景设计的静态数据结构，单查询复杂度可以做到O(logn + k)（k为最终返回的符合条件的元素个数），除了要返回的结果本身，额外的查询开销极低。

• 一次性初始化流程（总开销O(nlogn)）：
  1. 对当前的区间集合，选一个轴值（通常取集合内所有区间的中点平均值），把所有区间拆成三类：完全在轴值左侧的区间、完全在轴值右侧的区间、跨在轴值上（也就是from < 轴值 < to）的区间
  2. 把所有跨轴的区间，分别按from升序、to降序排成两个独立的有序列表，存在当前树节点上
  3. 对拆分出来的左、右区间集合，递归构建同样结构的子树
• 单次查询流程（给定x）：
  1. 从根节点开始，对比x和当前节点的轴值：
     • 若x < 轴值：遍历节点上按from升序排的跨轴区间列表，从开头往后筛选所有from <x的元素当结果，遇到第一个不符合条件的元素就停止扫描；随后递归进左子树继续查
     • 若x > 轴值：遍历节点上按to降序排的跨轴区间列表，从开头往后筛选所有to >x的元素当结果；随后递归进右子树继续查
     • 若x刚好等于轴值：直接返回节点上存的全部跨轴区间
  2. 整个过程不需要做任何跨集合求交运算，每一层节点只需要扫到第一个不符合条件的位置就停，整体效率远高于双集合求交的老方案。

低成本实现方案：分块索引 #

如果不想维护复杂的树结构，用分块法就能把之前的求交开销砍掉90%以上，实现逻辑非常简单。

• 一次性初始化流程（总开销O(nlogn)）：
  1. 把所有区间按from值升序排序，得到全局有序数组S
  2. 把S按固定大小（通常取256~1024个元素为一块，可根据内存调整）切成连续的块；对每个块内部，把块里所有元素的to值单独提取出来排好序，存成块的元信息
• 单次查询流程（给定x）：
  1. 用二分查找在S里定位最后一个满足from <x的位置k，S的前k个元素就是所有左端点符合要求的候选集合
  2. 把前k个候选元素拆成若干完整块 + 最后一个不完整的块
  3. 对每个完整块：在块内部已经排好序的to列表里，二分定位第一个to >x的位置，直接把块内这个位置之后的所有元素作为结果取出来（因为块内to已经有序，这些元素的to一定满足大于x的要求）
  4. 对最后那个不完整的块：直接逐个遍历元素，把满足to >x的元素加进结果
• 这个方案全程不需要维护单独的to排序数组，也不需要做大集合的求交运算，完整块的查询只需要二分，最后一个块的遍历量最多不超过块大小，相比之前两个大集合求交的方案，性能通常能提升几十到上百倍。

补充：如果你的查询点x的取值范围是可控的（比如集中在0到1e6的整数区间），可以直接做最朴素的预加载：初始化时为每个可能的x值建一个列表，遍历所有区间，把区间引用插入到所有它覆盖的x对应的列表里，查询时直接O(1)取结果就行，这是性能最高的实现方式，仅适合x取值范围有限的场景。

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