用于快速检查重叠范围的数字的数据结构

Question

假设我有以下数字范围:

0-500 0-100 75-127 125-157 130-198 198-200

现在,假设我需要能够检查任何给定的数字并查看它所在的范围.最有效地使用什么类型的数据结构来告诉,例如,数字100属于范围0-500,0 -100和75-127？我只想要一个包含起始值的二叉树吗？在这种情况下,树中的每个节点是否可以在该起始点保存包含每个范围的多个对象？

请注意,我只需要检索这个特定的应用程序,我真的不认为自己需要在进程中修改它,所以检索速度是我的首要任务.

谢谢!

Answer 1

你需要的是区间树。区间树是一个非常普遍的概念，并且在每个问题的节点中保留略有不同的数据。在您的情况下，每个节点都会保留一个输入间隔列表，这些间隔覆盖了节点所代表的间隔。