支持O(log²n)查询x>a且y>b点数的平面点集数据结构设计

针对静态平面点集的二维范围计数需求（统计x>a且y>b的点总数），最易实现、复杂度达标的方案是归并树结构，预处理时间O(n log n)，单次查询严格O(log²n)。 #

结构设计与预处理 #

你原本的双排序数组思路方向是对的，问题出在找到x阈值后逐点校验y的步骤，可以通过线段树嵌套有序数组的结构优化掉线性遍历的开销：

• 第一步：将所有点按x坐标升序排序，x值相同的点按y坐标升序排序，得到有序点序列P，单独提取序列中所有点的x值组成数组X，方便后续二分定位。
• 第二步：以序列P的下标为区间范围构建线段树（即归并树）：
  • 线段树的叶子节点对应P中的单个点，节点内仅存储该点的y值，自然是长度为1的有序数组
  • 线段树的内部节点对应P上的一段连续区间，节点内存储该区间所有点的y值组成的升序有序数组，直接通过归并左右子节点的两个有序数组得到，和归并排序的合并逻辑完全一致
    整个预处理过程总时间复杂度为O(n log n)：线段树共log n层，每一层所有节点存储的数组长度之和恰好为n，总存储空间也是O(n log n)。

Farther(a,b)查询流程 #

查询逻辑完全贴合初始思路，仅把逐点校验y的步骤替换为线段树上的二分统计：

1. 定位x阈值边界：在有序数组X上做二分查找，用bisect_right找到第一个满足x_i > a的下标pos。如果pos >= n说明没有满足x条件的点，直接返回0即可。此时所有下标在[pos, n-1]范围内的点，全部满足x>a的条件，问题转化为统计该下标区间内y值>b的点总数。
2. 线段树区间统计：将区间[pos, n-1]拆分为线段树上O(log n)个预存了有序y数组的节点，对每个拆分出的节点：
   • 在节点的升序y数组上做二分查找，找到第一个y值大于b的位置
   • 该节点内符合y条件的点数量 = 数组总长度 - 上述位置的下标
3. 把所有拆分节点的统计值累加，就是最终返回的结果。
   整个查询过程中，拆分区间得到O(log n)个节点，每个节点内做一次O(log n)复杂度的二分查找，总时间复杂度恰好为O(log²n)，完全满足要求。

核心逻辑伪代码参考

# 预处理
sort P by x ascending, then y ascending
X = [p.x for p in P]
merge_tree = build_segment_tree(P)  # 每个节点存对应区间的升序y数组

def Farther(a, b):
    pos = bisect.bisect_right(X, a)
    if pos >= len(P):
        return 0
    total = 0
    # 遍历区间拆分出的所有线段树节点
    for node in merge_tree.split_interval(pos, len(P)-1):
        y_list = node.sorted_y
        y_pos = bisect.bisect_right(y_list, b)
        total += len(y_list) - y_pos
    return total

动态场景扩展方案 #

如果后续需要支持动态插入、删除点的需求，可以替换为以下结构，同样能达到O(log²n)的查询复杂度：

• 树状数组/线段树套平衡树：先将x坐标离散化作为外层树状数组/线段树的下标，每个树节点挂载一棵按y值排序的平衡树，增删点时沿着外层树的路径更新对应平衡树，查询时拆分x区间后在每个平衡树上统计y>b的数量即可。
• 若所有查询可以提前离线获取（不需要即时应答），也可以用CDQ分治处理，空间复杂度更低，总时间复杂度同样为O((n+q)log²n)。

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