问用于存储长序列(大部分是连续的)整数的有效数据结构

EN

我想要一个数据结构来有效地存储一个长序列的数字。数字应该总是整整数，比方说朗克斯。

我想利用的输入(声称“效率”)的特点是，多头大多是连续的。可能会缺少值。并且这些值可以与无序交互作用。

我希望数据结构支持以下操作：

• addVal(n)：添加单个值，n
• addRange(n，m)：将n和m之间的所有值相加
• delVal(n)：删除单个值，n
• delRange(n，m)：删除n和m之间的所有值，包括
• containsVal( n )：返回结构中是否存在单个值n
• containsRange(n，m)：返回结构中是否存在n和m之间的所有值，包括

本质上，这是一种更具体的集合数据结构，它可以利用数据的连续性来使用小于O(n)内存，其中n是存储的值数。

显然，虽然我认为这样一个数据结构的有效实现需要我们在内部存储时间间隔，这是不可见的或与用户无关的。有一些间隔树分别存储多个间隔，并允许操作找到与给定点或间隔重叠的间隔数。但是从用户的角度来看，这应该完全像一个集合(除了基于范围的操作之外，这样可以有效地处理大量的添加和删除)。

示例：

dataStructure = ...
dataStructure.addRange(1,100) // [(1, 100)]
dataStructure.addRange(200,300) // [(1, 100), (200, 300)]
dataStructure.addVal(199) // [(1, 100), (199, 300)]
dataStructure.delRange(50,250) // [(1, 49), (251, 300)]

我的假设是，这最好通过一些基于树的结构来实现，但我对如何做到这一点还没有很好的印象。我想知道是否有一些常用的数据结构已经满足了这个用例，因为我不想重新发明轮子。如果不是，我想听听你认为如何最好地实现这一点。