什么数据结构可以用来存储和检索离散值范围？

Question

我有一个JavaScript程序，其中我将管理大量整数范围。在这个上下文中，范围只是一个起始值和一个结束值（或任何等价物，比如一个起始值和一个长度值），并具有对另一个对象的引用。这些范围可以重叠，并且可以相同（尽管引用的对象将不同）。

可能的起始值和结束值在0到4294967295之间（2的32次方-1或0xFFFFFFFF），虽然在该域中还有几个巨大的“空洞”，没有范围会覆盖它们，即使部分地覆盖。与可能性的域相比，大多数范围都非常小：我希望绝大多数长度均小于2000。

我最重要的用例是查找包含给定整数值的所有范围。大多数情况下，我预计查找将失败（没有包含给定值的范围）。

否则，我显然也需要添加元素（通常）和从中删除元素（很少）。偶尔，我还需要找到与给定范围重叠的所有范围，而不是包含单个值的所有范围。

我可以使用什么样的数据结构呢？在范围列表中进行线性搜索是不切实际的，因为大多数情况下查找会失败；而我需要非常、非常经常地进行查找。

- zneak

---

这些范围是由0和max_int限定的吗？还是-inf到inf？ - Joe Frambach

@kojiro，是的，[start, end]或[start, length]都可以。 - zneak

另外，您能否消除相同的范围和完全适合于另一个范围内的范围？ - kojiro

有多少区间？是数千，百万级别，还是可能是任何数字（即十亿级别）？ - pkr

你需要的是被称为区间树的数据结构。 - Dan D.

Answer 1

二叉树的键是起始（低）值。一旦找到一个键，您可以相对容易地查找更高和更低的值。

- cyber-monk

---

或者一棵每个节点都有16个子节点的树。它非常适合于值的范围。 - Joe Frambach

使用带有起始键的二叉树只是帮助我找到需要测试的最后一个范围，因为任何起始值低于我要查找的值的范围都有可能具有足够远的结束值来匹配。在平均情况下，这将减少我需要探索的元素数量一半，但仍然不够好。 - zneak

我的想法是找到包含搜索关键字的最低min的集合，然后查看具有较大mins的集合，收集结果，直到找到第一个不包含搜索关键字的min的集合，这样做有意义吗？ - cyber-monk

我不确定我理解了。您让我找到起点最小但仍然包含该值的范围，然后从那里开始搜索？如果是这样，我的整个问题就是以有效的方式找到此第一个范围。 - zneak

经过进一步的思考，我认为二叉树并不能直接解决您的问题，但您的解决方案肯定是基于树的。我建议您查看段树[http://en.wikipedia.org/wiki/Segment_tree]或区间树[http://www.dgp.toronto.edu/~jstewart/378notes/22intervals/]。 - cyber-monk

Answer 2

我喜欢使用System.Tuple来处理这种情况[或者F#列表，但是很少有人知道F#]。

如果范围是连续的，那么将起始和结束整数作为元组Tuple nums = (start, end)就很简单了。否则，将起始-结束作为元组的第一个条目，列表作为第二个条目可能适合您，Tuple nums = ((start, end), List)。

- Tom Mallard

---

在JavaScript中存储也非常简单，因为创建数组的语法非常简洁：var nums = [start, end]。但正如您从该评论中猜测的那样，这不是我的关注点。我正在寻找一种基于包含值查找范围集合中的范围的方法，并且线性搜索所有我管理的范围将无法解决问题。此外，我正在使用JavaScript，因此.NET类不是解决方案。 - zneak

Answer 3

如果您将所有范围的起始和结束存储在一个映射回范围索引的列表中，您可以按顺序n进行操作。例如，mylist = [{45：range1}，{47：range2}，{55：range1}，{57：range2}] 然后，您可以扫描列表并在第一次看到标记时设置布尔值为true，在第二次看到它时设置为false。当您找到比您更高的数字时，您可以知道自己在哪些范围内。您可以使用bisect进行插入O（logn），而删除和插入则为O（n）。祝好运！~Ben

- Ben

---

线性时间太贵了，因为我有很多范围，而且我经常查找的值不存在，这是线性搜索的最坏情况。 - zneak

Answer 4

尝试1：

保留两个二叉树，一个用于起始值，一个用于结束值。对于两个树的节点（或仅对于“结束”），都具有通过某个ID（范围的起始值）引用唯一范围的属性。

在“起始”树上进行二分搜索，以缩小列表到起始值小于或等于搜索值的范围。在“结束”树上执行相同操作，其中值大于或等于搜索值。找到来自两个树的节点的交集，这些范围包含您的搜索值。

您可以使用哈希映射/集合找到交集，以获得最佳性能。

尝试2：

如果您为键是起始和结束值共享的前几位保留了哈希列表会怎样呢？

因此，如果起始值为“11001101”，结束值为“11010010”，则键为“110”。每个键都将映射到共享该键的范围（起始和结束）的列表。

当搜索一个值以查看它们所在的范围时，例如 '00101111'，您需要在哈希列表中搜索大约 n 个不同的值，其中 n 是位数（在您的情况下为 32）。在这种情况下，您需要搜索 '00101111'、'0010111'、'001011' 等。对于每个匹配，您必须实际检查搜索值是否在范围内。

乍一看，我觉得平均而言，对于每个匹配，有一半会是误报，但如果命中次数很少，而且键越大，命中次数就越少，那么这应该不重要。

对于例如起始值为 '00101110' 和结束值为 '01100111' 的情况，存在一个小问题，因为键将是 '0'，这意味着会有大量的“误报”。更好的方法是使用两个不同的键，'001' 和 '01'，尽管我不确定您需要编写什么特定的算法来进行此优化。如果范围足够小并且可以解决或忽略此问题，则可以获得非常快速的查找，因为大多数键都相对较长且不匹配搜索。

- pkr

---

假设平均情况下，其中一半节点开始过早，另一半节点结束过早，由于我们需要处理两个部分，因此这几乎是在线性时间内执行的。 - zneak