我正在寻找一种数据结构，它可以帮助我找到包含给定点的最小间隔（ ( low , high ) 对）。间隔可以正确嵌套。例如：
在 (2,7), (2,3), (4,5), (8,12), (9,10) 中寻找第 3 点应该得到 (2,3)。
在数据结构的构建过程中，间隔的添加没有特定的顺序，具体来说，不是根据它们的嵌套。有没有一种好方法可以将此问题映射到搜索树数据结构？
问问题
73 次
1 回答
1
段树应该可以完成这项工作。在段树的节点中，您保留覆盖该节点的最短间隔的长度，以及对间隔本身的引用。在处理给定点的查询时，您只需返回该点的节点引用的区间。
于 2013-10-31T08:55:03.617 回答