如何在O(logn)时间内统计坐标均大于给定点的二维点数量

问题描述 #

给定一组二维点集合{(x₁,y₁), (x₂,y₂), ..., (xₙ,yₙ)}，以及其中一个点(xᵢ,yᵢ)，需要返回x坐标大于xᵢ且y坐标大于yᵢ的点的数量。
可用数据结构限定为：Array、List（含Linked List）、Stack、Queue、各类树（Binary、BST、AVL、B-tree）、Hash Table、Heap。要求查询时间复杂度为O(logn)，排序预处理时间不计入。

现有思路：已考虑将x坐标存入数组并使用二分查找定位x>xi的点，但不确定如何存储y坐标以维持O(logn)的查询复杂度，需要思路提示。

解决思路提示 #

1. 预处理：按x排序+后缀有序y集合 #

• 先把所有点按x坐标升序排序，通过二分查找可以快速定位到所有x>xi的点的起始位置（这部分你已经想到了）。
• 核心是给排序后的点维护后缀的y坐标有序结构：
  • 从后往前遍历排序后的点，逐个把y值插入到一个有序数组中（保持数组升序）。这样每个位置对应的有序数组，就是从当前点到末尾所有点的y值集合。
  • 查询时，找到x>xi的起始位置后，取出对应位置的有序y数组，用二分查找找到第一个大于yi的元素索引，数组长度减去该索引就是满足条件的点数量。
  • 也可以用AVL树/平衡BST替代有序数组：从后往前构建，每个位置对应一个包含后缀所有y值的平衡树，查询时直接调用树的“统计大于yi的节点数”功能，时间复杂度也是O(logn)。

2. 树状数组/线段树方案（适配二维偏序） #

• 先把所有点按x升序排序，同时对y坐标进行离散化（把y值映射到连续的整数索引，解决y范围过大的问题）。
• 从后往前遍历排序后的点，用树状数组（或线段树）维护y值的计数：每遍历一个点，就把该点的y值对应的计数+1。查询时，先找到x>xi的起始位置，再用树状数组查询所有y>yi的计数总和即可。
• 这种方案的查询操作是O(logn)，因为树状数组的查询和更新都是O(logn)级别。

3. 细节注意 #

• 处理x坐标相同的点：排序时要确保x=xi的点不被纳入统计范围，比如排序规则设为x < xi的在前，x > xi的在后，x=xi的放在中间，二分查找时直接跳过这部分。
• 如果y坐标有重复值，二分查找时要注意找的是第一个大于yi的元素，而不是大于等于，避免统计错误。

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