如果您不关心重复项，那么您的间隔是不重叠的。您需要创建一个维护该不变性的结构。如果您需要类似numIntervalsContaining（n）的查询，那就是另一个问题。
您可以使用BST来存储一对端点，就像在C
++中一样
std::set<std::pair<long,long>>。解释是每个条目对应于间隔
[n,m]。您需要弱排序-
这是左端点上通常的整数排序。单个
int或
long
n插入作为
[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)
。addRange（n，m）：，
O(log N)
过程类似。如果插入的间隔与另一个间隔不平凡，请合并间隔，以保持非重叠属性。O(n)
下面指出的是最坏情况下的性能，因为我们要插入的子间隔所消耗的子间隔数没有上限。delVal（n）：，这
O(log N)
也是O(n)
最坏的情况，因为我们不知道要删除的间隔中包含多少个间隔。- delRange（n，m）：删除n和m之间的所有值，包括：
O(log N)
- containsVal（n）：返回结构中是否存在单个值n：
O(log N)
- containsRange（n，m）：返回结构中是否存在n和m之间的所有值（包括端点）：
O(log N)
请注意，我们可以使用正确的add（）和addRange（）方法维护非重叠属性，而delete方法已经维护了该属性。我们需要
O(n)在最坏的情况下进行存储。
请注意，所有的操作都
O(log N)和插入的范围
[n,m]是不一样
O(m-n)或
O(log(m-n))之类的东西。
我假设您不在乎重复项，而只是会员资格。否则，您可能需要间隔树或KD树或其他东西，但它们与浮点数据更相关…
