data-structures - 非重叠整数范围的数据结构？

Question

记得曾经学过一个数据结构，把一组整数作为范围存储在树中，但是已经10年了，我已经记不起数据结构的名字了，对细节有点模糊。如果有帮助，它是一种在 CMU 教授的函数式数据结构，我相信 2002 年的 15-212(编程原理)。

基本上，我想存储一组整数，其中大部分是连续的。我希望能够有效地查询集合成员资格，有效地添加一系列整数，并有效地删除一系列整数。特别是我不要注意保留原始范围。如果相邻的范围合并为一个更大的范围会更好。

一个简单的实现是简单地使用通用集合数据结构，例如 HashSet 或 TreeSet，并在添加范围时添加范围内的所有整数，或者在删除范围时删除范围内的所有整数。但是当然，除了使添加和删除变慢之外，还会浪费大量内存。

我正在考虑一个纯粹的功能数据结构，但对于我目前的使用，我不需要它。 IIRC、查找、插入和删除都是 O(log N)，其中 N 是集合中的范围数。

那么，你能告诉我我想要记住的数据结构的名称，或者一个合适的替代方案吗？

Answer 1

我发现旧作业和我想到的数据结构是Discrete Interval Encoding Trees或简称节食。它们在 Diets for Fat Sets 中有详细描述, 马丁·厄维格。函数式编程杂志，卷。 8, No. 6, 627-632, 1998。它基本上是一个区间树，具有所有区间不重叠和不接触的不变量。 Hackage 中有一个 Haskell 实现.我希望 Scala 会有一个现有的实现，但我没有看到任何实现。

作业还包括另一种数据结构，他们称为递归间隔遮挡树 (RIOT)，它不是在每个节点只保留一个间隔，而是保留一个间隔，并从该间隔中删除另一个(可能为空的)RIOT。该任务包括基准测试，表明它在随机插入和删除方面比饮食做得更好。 AFAICT 它只是 TA 编造的东西，从未发布过，因为它似乎不再存在于 Internet 上的任何地方，至少不在该名称下。