如何高效查找包含单个/多个值z的区间[x[i],y[i]]的所有索引？

方案一：离线扫描线算法（适合已知所有z的场景） #

这是效率最高的离线处理方式，核心是把区间事件和z查询事件合并排序后批量处理：

• 预处理所有事件：
  • 对每个索引i，生成两个事件：(x[i], 'start', i)（区间开始，将i加入活跃集合）、(y[i], 'end', i)（区间结束，将i从活跃集合移除）
  • 对每个z值，生成查询事件：(z, 'query', z_index)（记录z的原始索引，方便后续映射结果）
• 排序所有事件：
  • 按事件的数值从小到大排序；若数值相同，end事件优先于query事件，query事件优先于start事件（确保z=y[i]时不被计入结果，z=x[i]时被正确计入）
• 遍历排序后的事件：
  • 维护一个当前活跃的索引集合（比如用哈希集合或动态数组）
  • 遇到start事件，将对应i加入活跃集合
  • 遇到end事件，将对应i从活跃集合移除
  • 遇到query事件，将当前活跃集合的副本存入对应z_index的结果中

时间复杂度：O((N+M)log(N+M))，其中M是z数组的长度，适合所有z提前已知的场景。

方案二：基于x排序的线段树/区间树（支持在线查询） #

如果需要处理动态生成的z值（无法提前获取所有z），可以通过预处理索引结构实现高效在线查询：

• 预处理步骤：
  • 将所有(x[i], y[i], original_index)按x[i]升序排序，得到数组sorted_pairs
  • 构建线段树，线段树的每个节点对应sorted_pairs的一个子区间，节点内存储该子区间中所有y[i]和对应的original_index，并将y[i]按升序排序
• 查询单个z的步骤：
  1. 用二分查找找到sorted_pairs中最后一个x[i]≤z的位置，得到候选区间范围[0, pos]
  2. 在区间范围[0, pos]内遍历线段树的节点，对每个节点的y排序数组，用二分查找找到第一个y[i]>z的位置，该位置之后的所有元素对应的original_index都是满足条件的索引，收集这些索引

时间复杂度：预处理O(NlogN)，单次查询O(log²N + K)（K是满足条件的索引数量），适合在线查询场景。

方案三：哈希分桶（轻量级预处理，适合数据分布均匀的情况） #

针对区间长度远小于整体范围的特点，可以用分桶大幅减少无效遍历：

• 预处理步骤：
  • 计算x数组的最小值min_x和最大值max_x，设置桶的大小为bucket_size = sqrt(max_x - min_x)（可根据实际数据分布调整）
  • 创建哈希桶，每个桶对应一个x的区间[min_x + k*bucket_size, min_x + (k+1)*bucket_size)，将所有(y[i], original_index)放入对应x[i]所在的桶中
• 查询单个z的步骤：
  1. 遍历所有x区间≤z的桶（包括z所在的桶）
  2. 在每个桶内遍历所有元素，筛选出y[i]>z的original_index，收集结果

时间复杂度：预处理O(N)，单次查询O(sqrt(N) + K)，实现简单，适合数据分布均匀的场景。

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