用于查询给定间隔是否由一组其他间隔包围的数据结构

Question

有数百万个不重叠的连续间隔，如[a，c]、[c，e]、[e，g）……它们以随机顺序发送给我，我想随时查询是否可以用接收到的这些连续间隔的组合来封闭其他给定间隔。

例如，我希望有一个方法来添加一个连续的间隔，一个方法来测试一个任意的间隔是否可以被之前添加的间隔组合所包围。

类似于

# add [a, c), [c, e)
my_interval_set.add([c,e])
my_interval_set.add([a,c])

my_interval_set.enclose([a,e])  # should return true

想知道什么是适合这种情况的数据结构？

如果有区别，我们可以假设i的边界总是与一些cs的边界匹配，因此在上面的示例中，不会有一个查询my_interval_集。当b在区间[a，c]内时，将其括起来（[b，d]）。

如果必须在两个操作的效率之间进行权衡，那么对我来说，include（）更重要。

我的尝试是使用插入排序和合并相邻间隔（如a，c，c，e）-

def add(c):
    idx = my_list.insert(c)  # insertion sort the interval c
    my_list.merge_if_adjacent(idx)  # check neighbour elements of c and merge if needed


def enclose(i):
    for interval in my_list:
        if interval.lo <= i.lo and interval.hi >= i.hi:
            return True
    return False

在最坏的情况下，add（）和enclode（）都是O（n）时间复杂度，这对我来说似乎效率很低，因为可能有数百万个连续的间隔需要添加和查询。

编辑：
根据btilly@的回答，写了一些伪代码作为我的注释

# assume a RBTree data structure with following operations
RBTree.insert(x, flag)
RBTree.delete(x)
RBTree.search(x) -> val, flag
RBTree.predecessor(x) -> val, flag
RBTree.successor(x) -> val, flag  # ref: https://baihuqian.github.io/2018-07-30-inorder-successor-in-bst/


def insert(tree, a, b):
    node_a = tree.search(a)
    node_b = tree.search(b)
    if not sanity_check(node_a, node_b):
        return False

    if node_a is None:
        tree.insert(a, START)
    else:
        tree.delete(node_a)

    if node_b is None:
        tree.insert(b, END)
    else:
        tree.delete(node_b)

def enclose(tree, a, b):
    node_a = tree.search(a)
    if node_a is None:
        node_a = tree.predecessor(a)
    node_b = tree.successor(node_a[0])
    if node_b[0] >= b:
        return True
    else:
        return False

def sanity_check(node_a, node_b):
    # node_a can only be None or an END node
    # node_b can only be None or a START node
    # no other nodes in between
    # ...

Answer 1

拥有某种endpoint的平衡二叉树，以及它们是开放的还是封闭的。

要插入[a， b]，您的逻辑如下所示：

let x be the last event before a (if any)
let y be the next event after b (if any)
delete all events between x and y (if any)
if x doesn't exist or is a close:
    insert (a, open) into the tree
if y doesn't exist or is an open:
    insert (b, close) into the tree

现在，插入一个区间可能会非常昂贵（因为您要处理的是一个长区间）。但是每个间隔的摊销成本是O（log（n）），因为这是查找的成本，如果需要插入的话插入的成本，以及以后删除的成本。

测试封闭的成本是O（log（n））。找到间隔开始之前或等于开始的最后一个事件。如果它是打开的，并且下一个事件是结束时或结束后的关闭，那么它是封闭的。否则不行。