algorithm - 具有重叠的限制之间的值的值查找图

Question

我正在尝试使用 map 来加速我的算法。基本上我正在寻找引用，因为我不知道如何用谷歌搜索我的问题。

我有一系列值的特定对象。现在我需要找到用于此值的对象。示例:

 x --->

|0 ---- object A ---- 100|                  |140 -- object D -- 200|
                 |80 -- object B -- 120|
         |50-object C-100|

因此，如果我想用 x = 10 做一些事情，我想得到 object A。如果我有 x = 90，我想得到 object A、object B 和 object C。

目前我正在运行所有对象的循环并检查它们的限制。但是在 x 中有一个顺序(显然)。我很确定(或至少希望)使用此命令来加快我的实现速度。类似于具有重叠限制的查找映射。

x 值的请求是在数字实现中完成的。它经常被调用(在 10'000 到 10'000'000 次之间，具体取决于精度、我的问题的网格大小、实际问题的大小......)。

PS:当我尝试用谷歌搜索时，我只找到关于谷歌地图或普通查找表的信息。如果你有我可以用谷歌搜索的东西，我也很高兴。

Answer 1

您正在搜索 interval tree .它们是特殊类型的二叉树，比传统的线性查找效率高得多，后者需要 O(N) 的查找时间。区间树只需要:

Queries require O(log n + m) time, with n being the total number of intervals and m being the number of reported results. Construction requires O(n log n) time, and storage requires O(n) space.

由于在标准算法教科书(Cormen、Leiserson、Rivest 和 Stein 的“An introduction to algorithms”)中对其进行了描述，您会在网上找到大量用不同语言编写的示例，其中 CLRS 版本用作引用实现。