排序间隔查询

Question

我正在寻找一种数据结构,它可以在封闭的时间间隔内有效地运行,具有以下属性:

• 动态添加或删除间隔

• 设置并随时更改每个间隔的数字("深度").没有两个深度是一样的

• 查找与任何给定间隔重叠的所有间隔,按"深度"排序

我找到的最接近的结构是Interval树,但是它以相对于它们的深度的任意顺序列出了找到的间隔.我可以收集所有报告的"未排序"间隔,然后对它们进行排序,但我跳过它可以避免为每个查询排序结果.

请问,有没有人知道这样的数据结构或有任何建议如何(如果可能的话)增强Interval树来支持这样的排序？

例:

1. 将[1,2]添加到空结构并将其深度设置为1
2. 添加[10,100],深度= 2
3. 添加[5,55],深度= 3
4. 查询[5,50]报告[10,100]和[5,55]
5. 将[10,100]的深度设置为3,将[5,55]设置为2
6. 查询[5,50]报告[5,55]和[10,100]

编辑

我对快速添加/删除和查询更感兴趣,而不是更新深度.深度可以与O(n)一样多,如果这有助于加速其他操作.

Answer 1

假设您想要的算法存在。然后，我们创建一百万个间隔的集合，每个间隔为[1, 1]，具有随机深度，并将其插入到这样的间隔树中。然后让我们查询一下时间间隔[1, 1]。它应按排序顺序返回所有间隔O(M + log N)，但复杂度为N = 1，因此，我们将M在线性时间内对一组元素进行排序。

换句话说，从间隔树中获取元素后，按深度对元素进行排序就其复杂性而言在理论上是可行的。

Answer 2

您设置的深度相当于其虚数中间隔的位置list。因此，通常的数字对列表就足够了。列表可以轻松添加、删除或切换其项目。

如果您还需要找到给定间隔的深度，请为其创建一个函数（尽管您没有提到需要）