处理区间的数据结构

问题描述

我有一系列不能重叠的时间间隔 (t_start,t_end)，即:t_end(i) > t_start(i+1).我想做以下操作:

I have got a series of time intervals (t_start,t_end), that cannot overlap, i.e.: t_end(i) > t_start(i+1). I want to do the following operations:

1) 添加新的 (Union of) 区间 [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) 取出区间 [ (1,7) - (3,5) = {(1,3),(5,7)}
3)检查一个点或一个区间是否与我的系列中的一个区间重叠(交集)
4) 在某个点 [ {(1,4),(7,8)}: 4 和 7 之间存在长度为 3 的非间隔"].

1) Add new (Union of) intervals [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) Take intervals out [ (1,7) - (3,5) = {(1,3),(5,7)}
3) Checking whether a point or a interval overlaps with an interval in my series (intersection)
4) Finding the first "non-interval" of a minimum length after some point [ {(1,4),(7,8)}: there is a "non-interval" of length 3 between 4 and 7 ].

我想知道实现这一点的好方法，复杂度低(所有操作的 log n 都可以).

I want to know good ways of implementing this, with low complexities (log n for all operations would do it).

相关问题:快速时间间隔查找的数据结构

推荐答案

听起来你可以只使用所有边界时间的平衡二叉树.

It sounds like you could just use a balanced binary tree of all the boundary times.

例如，将 {(1,4), (8,10), (12,15)} 表示为包含 1、4、8、10、12 和 15 的树.

For example, represent {(1,4), (8,10), (12,15)} as a tree containing 1, 4, 8, 10, 12, and 15.

每个节点都需要说明它是间隔的开始还是结束.所以:

Each node needs to say whether it's the start or end of an interval. So:

                          8 (start)
                         /
                1 (start)         12 (start)
                                   /
                     4 (end)   10 (end)   15 (end)

(这里所有的结束"节点巧合地都在底部.)

(Here all the "end" nodes ended up at the bottom by coincidence.)

那么我认为您可以在 O(log n) 时间内完成所有操作.添加间隔:

Then I think you can have all your operations in O(log n) time. To add an interval:

• 找到开始时间.如果它已经在树中作为开始时间，您可以将其留在那里.如果它作为结束时间已经在树中，您将需要将其删除.如果它不在树中并且它在现有时间间隔内没有落下，则您需要添加它.否则你不想添加它.

• Find the start time. If it's already in the tree as a start time, you can leave it there. If it's already in the tree as an end time, you'll want to remove it. If it's not in the tree and it doesn't fall during an existing interval, you'll want to add it. Otherwise you don't want to add it.

找到停止时间，用同样的方法找出是否需要添加，删除它，或者都不需要.

Find the stop time, using the same method to find out if you need to add it, remove it, or neither.

现在您只想添加或删除上述启动和停止节点，同时删除其间的所有现有节点.为此，您只需要在树中的这两个位置或正上方重建树节点.如果树的高度是 O(log n)，你可以使用平衡树来保证，这需要 O(log n) 时间.

Now you just want to add or remove the abovementioned start and stop nodes and, at the same time, delete all the existing nodes in between. To do this you only need to rebuild the tree nodes at or directly above those two places in the tree. If the height of the tree is O(log n), which you can guarantee by using a balanced tree, this takes O(log n) time.

(免责声明:如果您使用 C++ 并进行显式内存管理，那么在执行此操作时您最终可能会释放超过 O(log n) 块的内存，但实际上释放节点所需的时间应该是我想是向添加它的人收费.)

(Disclaimer: If you're in C++ and doing explicit memory management, you might end up freeing more than O(log n) pieces of memory as you do this, but really the time it takes to free a node should be billed to whoever added it, I think.)

删除间隔大致相同.

检查点或区间很简单.

在给定时间后找到至少给定大小的第一个间隙也可以在 O(log n) 中完成，如果您还为每个节点缓存另外两条信息:

Finding the first gap of at least a given size after a given time can be done in O(log n) too, if you also cache two more pieces of information per node:

• 在每个起始节点(除了最左边)，紧靠左边的间隙的大小.

• In each start node (other than the leftmost), the size of the gap immediately to the left.

在每个节点中，出现在该子树中的最大间隙的大小.

In every node, the size of the largest gap that appears in that subtree.

要找到给定时间后出现的给定大小的第一个间隙，首先在树中找到那个时间.然后向上走，直到到达一个声称包含足够大间隙的节点.如果你从右边上来，你知道这个缺口在左边，所以你忽略它并继续向上走.否则你是从左边来的.如果该节点是起始节点，请检查其左侧的间隙是否足够大.如果是这样，你就完成了.否则，足够大的间隙必须在右侧的某处.向右走，继续向下，直到找到间隙.同样，因为树的高度是 O(log n)，所以走三遍(向下，向上，可能再次向下)是 O(log n).

To find the first gap of a given size that appears after a given time, first find that time in the tree. Then walk up until you reach a node that claims to contain a large enough gap. If you came up from the right, you know this gap is to the left, so you ignore it and keep walking up. Otherwise you came from the left. If the node is a start node, check to see if the gap to its left is large enough. If so, you're done. Otherwise, the large-enough gap must be somewhere to the right. Walk down to the right and continue down until you find the gap. Again, because the height of the tree is O(log n), walking it three times (down, up, and possibly down again) is O(log n).

这篇关于处理区间的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！