data-structures - 有效允许拉取所有范围(最小值、最大值)的最佳数据结构，使得值 >= 最小值和值 <= 最大值？

Question

假设我有一组最小值和最大值。我想要一个数据结构，在给定外部值的情况下，它会最有效地为我提供值 >= 最小值、值 <= 最大值的 (min,max) 对。

如果您知道范围是不重叠的，我想您可以在 min 上做一个平衡的二叉搜索树，并且满足 (min,max) 的第一个节点必须是唯一的。但是，如果范围可以重叠，是否有一种数据结构可以让您高效地做到这一点？

Answer 1

您描述的问题也称为“刺穿查询”。它在图形编程教科书中有很好的描述，这是一个非常相关的问题。

此外，segment trees 上的维基百科页面可能有帮助。这些树是通常用于解决此问题的数据结构。