离线查询场景下，如何高效统计任意直线上的点数量？

核心思路：避免单查询全量遍历 #

要突破单查询O(N)的瓶颈，核心是通过预处理或离线批量处理，把重复计算的部分提前完成，或者将同类查询合并处理。

1. 预处理特殊直线的快速查询 #

对于两类特殊直线，可以直接用哈希表实现O(1)查询：

• 垂直直线（x=k）：统计每个x坐标出现的次数，用哈希表count_x存储，键为x值，值为对应点的数量。查询x=k时直接返回count_x.get(k, 0)。
• 水平直线（y=k）：同理，用哈希表count_y统计每个y坐标的出现次数，查询y=k时直接返回count_y.get(k, 0)。

2. 离线批量处理方案（适合已知所有查询的场景） #

如果所有查询提前可知，这是最有效的优化方式：

• 步骤1：将所有查询按斜率m分组，相同m的查询放在同一组。
• 步骤2：对每个m组：
  • 遍历所有点，计算key = y - m*x，用哈希表统计每个key对应的点数量。
  • 遍历该组内的所有查询(m, c)，直接返回统计结果中key=c的数值。
• 时间复杂度：O(NM + Q)，其中M是查询中不同m的数量，Q是总查询数。当M远小于Q时，效率远高于O(QN)。

3. 在线查询的优化：哈希集合+剪枝 #

如果无法离线处理，可结合哈希集合减少无效计算：

• 预处理：将所有点存入哈希集合points（比如用元组(x,y)作为元素）。
• 查询时：
  • 先估算直线上可能存在的点的范围（比如根据所有点的x坐标极值，确定x的取值范围）。
  • 遍历该范围内的整数x，计算对应的y = m*x + c，检查(x,y)是否在points中，统计数量。
• 优势：如果直线上的点稀疏，实际遍历的次数远小于N；但如果直线穿过大部分点，效率仍接近O(N)。

关于QuadTree的说明 #

QuadTree这类空间划分结构并不适合该问题：直线可以穿过QuadTree的多个分区，每个分区都需要遍历检查，无法避免全量或接近全量的点扫描，因此无法突破O(N)的单查询复杂度。

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