计数矩形中的点

将点表示为kd树。

也就是说，可以将其中每个节点代表一个点且每个非叶节点的二叉树视为在该节点的x或y值上垂直或水平（或者在每个级别上）划分当前区域。

然后，进行查询：

1. 当前节点=根

2. 当前面积=当前节点的面积（可以在沿着树递归时跟踪/计算）

3. 如果当前区域完全包含在矩形内，则添加此节点作为子节点的点数（当前节点为+1）。

4. 如果当前区域完全在矩形内部，则什么也不做。

5. 如果当前区域部分包含在矩形内：

   • 如果当前节点的点包含在矩形中，则将其添加。
   • 对两个孩子重复从2开始的 *** 作。

计算矩形中是否包含区域或点应该足够简单。

每个查询对随机数据平均应花费O（log n）时间。

尽管在某些病理情况下，这将花费O（n）时间（即，您将需要探索整个树/大部分树）。这种情况的一个可能的示例是，大多数点都围绕（非轴对齐的）矩形的边缘（内部或外部），这意味着上面提到的“不执行任何 *** 作”部分将很少适用。