查询给定区间是否被一组其他区间包围的数据结构

Data structure for querying if a given interval is enclosed by a set of other intervals

有数百万个不重叠的连续间隔,例如 [a, c), [c, e), [e, g)... 它们以 随机顺序 发送给我,我想随时查询其他给定间隔是否可以包含在收到的那些连续间隔的组合中。

例如,我希望 my_interval_set 有一个方法 add(c) 来添加一个连续的间隔 c,一个方法 enclose(i) 来测试任意间隔是否i可以用前面加的区间组合括起来

类似

# 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 的边界将始终与某些 c 的边界匹配,因此在上面的示例中不会有查询 my_interval_set.enclose([b,d]) 因为 b 落在 [a,c] 区间内。

如果必须在两个操作的效率之间进行权衡,enclose()对我来说更重要。


我的尝试是使用插入排序并合并相邻区间(如[a,c)+[c,e] -> [a,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()enclose() 都是 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
    # ...

拥有某种端点的平衡二叉树以及它们是打开还是关闭。

要插入 [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))。查找间隔开始之前或等于间隔开始的最后一个事件。如果它是开盘,而下一个事件是在结束时或结束后结束,那么它是封闭的。否则不行。