arrays - 矩形中的点数

Question

我有 N 个点，用 (xi,yi) 表示。

1<=i<=N

我有以下形式的 Q 查询:

给定一个由点 x1, y1, x2, y2 定义的矩形(与 x,y 轴对齐)，其中 (x1, y1) 是左下角，(x2, y2) 是右上角，找到矩形内的点数。矩形上的点被认为在外面。

Constraints :
1 ≤ N ≤ 100 000
1 ≤ Q ≤ 100 000
0 ≤ xi, yi ≤ 100 000
0 ≤ x1 < x2 ≤ 100 000
0 ≤ y1 < y2 ≤ 100 000

我想到了以下方法:

1. 在 N*N 矩阵上构建二维线段树。一个查询将在 log N 时间内得到解决。但是构建的线段树的大小会>=10^7。因此内存不足。

2. 保留两个数组(比如 X 和 Y)，两个数组都包含所有 N 个点。X 根据 x 坐标排序，Y 根据 y 坐标排序。现在给定 x1,y1,x2,y2:我可以在 log N 时间内从 X 数组中找到所有 >=x1 && <=x2 的点。同样，我可以在 log N 时间内从 Y 中找到所有 >=y1 && <=y2 的点。但是如何找到给定矩形中的点数，我无法进一步研究!

复杂度应为 O(NlogN) 或 O(QlogN)

Answer 1

这个问题叫做正交范围搜索:

Given a set of n points in R^d, preprocess them such that reporting or counting the k points inside a d-dimensional axis-parallel box will be most efficient.

您的查询是范围计数查询(不是范围报告查询)。

二维范围树可用于使用 O(n log n) 存储在 O(log n) 时间内回答范围计数查询(参见示例 Ch.36 of Handbook of Discrete and Computational Geometry 2Ed, 2004)

如果您的 x 和 y 在网格上，并且网格很窄，请参阅 Orthogonal range searching in linear and almost-linear space [Nekrich, 2009]其中提供了 O((logn/log logn)²) 时间数据结构。