范围最小/最大查询

我有坐标点（x，y）说我有10000点。现在当一个新点被给出为测试查询说（p，q）时。我要检查每点坐标points.if X文本查询是坐标 PY 从网上搜索我才知道，Rmq-范围最小/最大的查询数据结构可以帮助我，但我不知道该怎么办呢..can有人帮助我如何可以我这样做..any引用或C++代码的帮助将是很大的帮助。谢谢范围最小/最大查询

来源

2011-08-25 Nichole Grace

你能澄清你在问什么吗？你想对测试点做什么？你想找到最接近它的地方吗？你是否试图检查数据集中是否存在该点？ – templatetypedef

我试图找到，如果数据集中 –

点退出更准确地说我试图让。那是，如果在与后缀数组检查..一个字符串，然后它给包围了所有后缀范围的输入文本的后缀数组范围。现在我设法得到后缀输入文本的后缀数组的范围。现在我试图看看输入文本的后缀范围是测试字符串的前缀。要测试这个，我可能不得不使用rmq或一些好的数据结构来检查这种情况的时间效率 –

如果你的目标是要检查数据集是否存在该点，则有是一些可用于保存数据的非常有用的数据结构，每个数据结构都支持非常高效的查找。

对于初学者来说，如果你需要知道的就是点是否存在，你总是可以存储在一个标准的哈希表或平衡二叉搜索树中的所有点。这将分别提供O（1）或O（log n）查找时间。再加上这些结构在大多数编程语言中都是可用的。另一方面，如果您计划对数据进行更有趣的操作，例如搜索距离某个测试点最近的数据集中的k个点，或试图找到某些边界中的所有点区域，您可能需要考虑使用kd-tree或quadtree。这些标准二进制搜索的变体提供了快速查找（O（log n）时间）。 kd-tree还支持非常快速的k-nearest-neighbor searches并在边界卷内进行搜索。此外，如果您有任何实现标准二叉搜索树的经验，kd-tree会非常容易实现。

希望这会有所帮助！

来源

2011-08-25 00:58:57 templatetypedef

范围最小/最大查询

回答

相关问题