保存点的数据结构( x_i，y_i)和查找x_i>a& y_i >b的所有点的过程

Question

给定一个平面上的N个点(x_1，y_1)，.，(x_n，y_n)，需要描述一个包含所有点的DS ( x_i，y_i)和一个更远的过程(a，b)，该过程将在O(log^2(n))的时间复杂度范围内返回满足x_i>a& y_i > b的DS中所有点的数目。

我想要实现的基本上是一个DS，它有两个平面上点的排序数组，而第一个数组是根据x值排序的，第二个数组是根据y值排序的。然后，通过二进制搜索最小满足x值，检索所有满意点，然后检验这些点是否满足y值。这是直观的解决方案，但它需要O(nlogn)时间。

不幸的是，没有找到一个更好的解决方案。

Answer 1

只要您不需要动态更新结构，我认为标准解决方案是部分持久的红黑树或类似的搜索树。

部分持久数据结构是一种可以在不失去对以前版本访问权限的情况下被修改的。这些在像Haskell这样的纯功能语言中非常常见--因为每个对象都是不可变的，“修改”只是与旧版本尽可能多地共享数据的新版本，而且所有版本仍然可以使用。克里斯·冈崎的红黑树很受欢迎。

因此，考虑到一棵部分持久的红黑树，这个问题很容易解决：

1. 按X反序排序
2. 将点插入树中，按Y排序，并跟踪为每个点创建的版本。

现在，当您需要找到X>a和Y>b的所有点时：

1. 在X排序点列表中进行二进制搜索，以找到最后一个带有X>a的点。
2. 获取关联的树版本，它只包含带有X>a的点。
3. 从最大Y开始遍历这棵树，如果你找到一个带有Y<=b的树，就停下来。

就是这样--非常简单，只是树结构本身有点棘手，很难在某些语言中找到库版本。每个搜索都需要O(log )时间，数据结构本身根据实现的不同而占用O(N)或O( N )空间。

K-d树也可以用来解决这个问题，虽然它们没有提供相同的复杂性保证，但性能通常很好。