我想要一种数据结构来有效地存储一长串数字。数字应该始终是整数，比方说Longs。
我想利用（声称“效率”）输入的特征是多头将 大部分是 连续的。可能缺少值。并且这些值可以不按顺序交互。
我希望数据结构支持以下操作：
从本质上讲，这是一种更特定的Set数据结构，可以利用数据的连续性来使用少于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)]
我的假设是最好通过某些基于树的结构来实现，但是我对如何做到这一点还没有很好的印象。我想了解是否存在一些已经满足此用例的常用数据结构，因为我不想重蹈覆辙。如果没有，我想听听您如何认为最好的实施方式。
如果您不关心重复项，那么您的间隔是不重叠的。您需要创建一个维护该不变性的结构。如果您需要类似numIntervalsContaining（n）的查询，那就是另一个问题。
您可以使用BST来存储一对端点，就像在C ++中一样std::set<std::pair<long,long>>。解释是每个条目对应于间隔[n,m]。您需要弱排序- 这是左端点上通常的整数排序。单个int或long n插入作为[n,n]。我们必须维护所有节点间隔都不重叠的属性。对操作顺序的简要评估如下。既然您已经指定了，n我将使用N树的大小。
std::set<std::pair<long,long>>
[n,m]
int
long
n
[n,n]
N
addVal（n）：添加单个值n：，O(log N)与a相同std::set<int>。由于间隔是不重叠的，因此您需要找到的前任n，可以及时完成O(log n)（按https://www.quora.com/How-can-you-find-successors-和前辈按顺序进行二进制搜索树）。查看此前任节点的右端点，并根据需要延长间隔或添加其他节点[n,n]，按照左端点顺序，该节点始终是正确的子节点。请注意，如果间隔被扩展（插入[n+1,n+1]树中，其中节点[a,n]构成节点[a,n+1]），它现在可能会碰到下一个左端点，因此需要再次合并。因此，需要考虑一些边缘情况。比简单的BST稍微复杂一点，但仍然如此O(log N)。
O(log N)
std::set<int>
O(log n)
[n+1,n+1]
[a,n]
[a,n+1]
addRange（n，m）：，O(log N)过程类似。如果插入的间隔与另一个间隔不平凡，请合并间隔，以保持非重叠属性。O(n)下面指出的是最坏情况下的性能，因为我们要插入的子间隔所消耗的子间隔数没有上限。
O(n)
delVal（n）：，这O(log N)也是O(n)最坏的情况，因为我们不知道要删除的间隔中包含多少个间隔。
请注意，我们可以使用正确的add（）和addRange（）方法维护非重叠属性，而delete方法已经维护了该属性。我们需要O(n)在最坏的情况下进行存储。
请注意，所有的操作都O(log N)和插入的范围[n,m]是不一样O(m-n)或O(log(m-n))之类的东西。
O(m-n)
O(log(m-n))
我假设您不在乎重复项，而只是会员资格。否则，您可能需要间隔树或KD树或其他东西，但它们与浮点数据更相关…
