我记得学过一种数据结构，将一组整数作为范围存储在树中，但是已经 10 年了，我不记得数据结构的名称，而且我对细节有点模糊。如果有帮助，它是 CMU 教授的一种函数式数据结构，我相信 2002 年的 15-212（编程原理）。
基本上，我想存储一组整数，其中大部分是连续的。我希望能够有效地查询集合成员资格，有效地添加整数范围，并有效地删除整数范围。特别是，我不在乎保留原始范围。如果将相邻的范围合并为一个更大的范围，那就更好了。
一个简单的实现是简单地使用一个通用的集合数据结构，例如 HashSet 或 TreeSet，并在添加范围时添加范围中的所有整数，或者在删除范围时删除范围中的所有整数。但是当然，除了使添加和删除速度变慢之外，这还会浪费大量内存。
我正在考虑一个纯粹的函数式数据结构，但就我目前的使用而言，我不需要它。IIRC、查找、插入和删除都是 O(log N)，其中 N 是集合中的范围数。
那么，你能告诉我我想记住的数据结构的名称，还是一个合适的替代方案？
我发现我想到的旧作业和数据结构是离散间隔编码树或简称节食。脂肪组饮食中详细描述了它们，Martin Erwig。函数式编程杂志，卷。8, No. 6, 627-632, 1998. 它基本上是一棵区间树，所有区间不重叠且不接触。Hackage中有一个 Haskell 实现。我希望 Scala 会有一个现有的实现，但我没有看到任何实现。
作业还包括另一个他们称为递归间隔遮挡树 (RIOT) 的数据结构，它不是在每个节点处仅保留一个间隔，而是保留一个间隔，并从间隔中删除另一个（可能为空的）RIOT。该任务包括基准显示它比随机插入和删除的饮食做得更好。AFAICT 它只是 TA 编造的东西，从未发布过，因为它似乎不再存在于 Internet 上的任何地方，至少不以该名称存在。
您可能正在寻找线段树。这可能会有所帮助：http ://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
您也可以使用二叉搜索树，每个节点都有两个数据字段：min_val 和 max_val。
在插入算法中，只需要调用另一个合并操作来检查左孩子、父母、右孩子是否创建了一个序列，从而将它们组合成一个节点。这将花费 O(log n) 时间。
其他操作如删除和查找将像往常一样花费 O(log n) 时间，但删除时需要采取特殊措施。