c++ - 范围最小值/最大值查询

Question

我有坐标点 (x,y) 说我有 10 000 点。现在当一个新点作为测试查询给出时说(p，q)。我必须检查坐标点中的每个点。如果文本查询的 x 坐标是 PY通过在线搜索，我了解到 Rmq- range min/max 查询数据结构可以帮助我，但我不确定该怎么做。有人可以帮助我吗，我该怎么做。C++ 中的任何引用或代码帮助都会很有帮助。谢谢

Answer 1

如果您的目标是检查数据集中是否存在该点，那么您可以使用许多非常有用的数据结构来保存数据，每个数据结构都支持非常高效的查找。

对于初学者来说，如果您只需要知道点是否存在，您总是可以将所有点存储在标准哈希表或平衡二叉搜索树中。这将分别提供 O(1) 或 O(log n) 查找时间。此外，这些结构往往适用于大多数编程语言。

另一方面，如果您计划对数据进行更奇特的操作，例如在数据集中搜索距离某个测试点最近的 k 个点，或者试图找到某个边界区域中的所有点，您可能需要考虑使用 kd-tree或 quadtree .标准二进制搜索的这些变体提供快速查找(O(log n) 时间)。 kd-tree 也支持非常快的 k-nearest-neighbor searches并在边界体积内搜索。此外，如果您有任何实现标准二叉搜索树的经验，则 kd 树实现起来非常容易。

希望这对您有所帮助!