algorithm - 区间树查询

Question

给定一组 N 个区间:对于每个区间，哪个区间具有最大重叠？

例如{ [0,5], [2,9], [2,3], [4,9] } :

[0,5]: [2,9](4 的重叠)

[2,9]: [4,9](6 的重叠)

[2,3]:[0,5] 或 [2,9](2 的重叠)

[4,9]: [2,9](6 的重叠)

N 可以很大，所以我认为间隔树是必要的。但是，我发现没有任何帖子或出版物描述了此类查询的方法。查询的结果可以位于区间树节点(中心左侧、重叠中心、中心右侧)的 3 条路径中的任何一条上，因为它们可能包含也可能不包含查询区间的中心点。因此，我想不出一个 log(N) 遍历方法来获得结果。

此外，对于 [2,3] 的情况，我不在乎选择哪个。可以任意选取任何最大相交间隔。每次查询仅返回 1 个结果。

能否在log(N)中回答每一个问题，提供一个Nlog(N)的整体解决方案？

编辑:我制定的伪代码:

query(ITnode node, Interval intrv){
    // s_list: start-sorted intervals overlapping center
    // e_list: end-sorted intervals overlapping center
    if intrv.end < node.center:
        node_max = search node.s_list for interval w/ closest start to intrv.start
        return max(node_max, query(node.left_tree, intrv))
    else if intrv.start > node.center:
        node_max = search node.e_list for interval w/ closest end to intrv.end
        return max(node_max, query(node.right_tree, intrv))
    else: // Query overlaps center
        // Still working this out but I get the picture now
}

for each Interval i:
    result[i.id] = query(root, i)

Answer 1

我们可以使用区间树来解决这个问题。

算法:

1. 构造一组点 S - 合并区间的所有左右点。对于示例 S = {0, 2, 3, 4, 5, 9} 的输入。复杂度 - O(NlogN)

2. 构建具有以下结构的区间树

   结构树{ int max_overlap_value; int max_overlap_id; int second_max_overlap_value; int second_max_overlap_id; 树*左； 树*对； };

   同时设置 max_overlap_value = second_max_overlap_value = 0, max_overlap_id = second_max_overlap_id -1。复杂度 - O(N)

3. 使用输入的间隔更新树节点中的值。复杂度 - O(NlogN)

4. 为每个间隔找到 max_overlap_value、max_overlap_id、second_max_overlap_value、second_max_overlap_id。如果 max_overlap_id 等于 interval_id，则使用 second_max_overlap_value，否则使用 max_overlap_value。复杂度 - O(NlogN)

总复杂度为 O(NlogN)