具有重叠的限制之间的值的值查找图
Value lookup map for values between limits with overlap
我正在尝试使用地图加快我的算法。基本上我正在寻找参考，因为我不知道如何 google 我的问题。
我有一系列值的特定对象。现在我需要找到用于此值的对象。示例：
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：当我尝试 google 时，我 仅 找到有关 google 地图或普通查找表的信息。如果你有什么我可以google，我也很高兴。
您正在搜索 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 版本用作参考实现。
我正在尝试使用地图加快我的算法。基本上我正在寻找参考，因为我不知道如何 google 我的问题。
我有一系列值的特定对象。现在我需要找到用于此值的对象。示例：
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：当我尝试 google 时，我 仅 找到有关 google 地图或普通查找表的信息。如果你有什么我可以google，我也很高兴。
您正在搜索 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 版本用作参考实现。