dictionary - 哪些数据结构允许在嵌套间隔中进行有效查找？

Question

我正在寻找一种数据结构，它可以帮助我找到包含给定点的最小间隔（ ( low ,  high ) 对）。间隔可以正确嵌套。例如：

在 (2,7), (2,3), (4,5), (8,12), (9,10) 中寻找第 3 点应该得到 (2,3)。

在数据结构的构建过程中，间隔的添加没有特定的顺序，具体来说，不是根据它们的嵌套。有没有一种好方法可以将此问题映射到搜索树数据结构？

Answer 1

段树应该可以完成这项工作。在段树的节点中，您保留覆盖该节点的最短间隔的长度，以及对间隔本身的引用。在处理给定点的查询时，您只需返回该点的节点引用的区间。