家庭作业
我需要使用数据结构+算法返回由2个（x，y）值组成的范围内的元素数量（即返回在xy平面上的矩形范围内的元素数量）在O（logn *登录）。
我正在考虑两种可能性，kd-tree 和 range 树。kd-tree 非常适合这种情况，因为它可以在 O(logn + k) 范围内找到元素（对于需要报告的 k 个元素）。但我不需要报告元素，我只需要计算范围内的元素数量。
范围树可以在其中工作，我可以在每个节点中拥有一个属性，该属性包含多少小于自身。这样，我可以确定有多少元素小于 O(logn) 次中的特定值（通过转到两个边界并找到彼此小于的节点数的差异）。但是，我认为这不适用于同时具有 (x,y) 维度的数据集。
我在正确的轨道上吗？
您所描述的是一个在线二维正交范围计数问题。“在线”表示数据经过预处理后，查询接踵而至。“正交”表示范围是轴对齐的矩形。而且，与范围报告相反，范围计数仅计算范围内的项目数。
在最坏的情况下，每个节点存储其下节点总数的 kd 树可以在 O(n^(1-1/k)) 中执行范围计数。这是因为任何正交范围最多可以与 kd 树的 O(n^(1-1/k)) 个叶子相交。在二维情况下，意味着可以在 O(sqrt(n)) 中执行范围计数查询，这比所需的 O((log(n))^2) 更差。
您的第三段没有意义，因为范围树是在高维中定义的。事实上，它是高维正交范围计数问题的教科书解决方案。它在 O((log(n))^2) 查询时间内解决了在线二维正交范围计数。我建议您阅读由 Jon Louis Bentley 撰写的一篇开创性论文Multidimensional Divide-and-Conquer ，他是独立发现范围树的几个人之一。相关部分为 2.1.2。
由于这是一个家庭作业问题，我不会详细说明，但我可能已经说得太多了。