algorithm - 处理闭区间的数据结构

Question

当我发现我无法处理的问题时，我正在学习测试：

设计一个用于处理（闭合）区间的数据结构，它将提供三个操作：

Insert(x,y) - 添加区间 [x, y]

Remove(x,y) - 删除区间 [x, y]

Count(x,y) - 计算纯粹包含在区间 [x, y] 内的区间数

x,y 是从 1 到 n 的整数。所有操作最多花费时间 O((log n) ² )

任何人都可以帮忙吗？

Answer 1

这可以使用Fenwick 树和基于分段树的数据结构在 O(log^2 n) 时间和 O(nlog n) 空间中解决，分段树在每个节点内都包含一个内部树。前者用于有效地查找和更新给定范围内的点数；后者用于有效地查找和更新跨越给定点的段数。基本思想是计算给定查询范围内的段端点，然后针对跨越一个或两个端点的段进行调整。

该算法基于以下观察：对于给定的查询范围 (a, b)，

nContained = (h - nStraddlingOne) / 2

其中 nContained 是 (a, b) 包含的区间数，h 是 (a, b) 中任一类型（开始或结束）的区间端点数，nStraddlingOne 是仅包含 a 或只有 b。任何时间间隔的“数据库”在这里称为 D。

Fenwick 树允许您使用 O(n) 表在 O(log n) 时间内计算两个整数索引 (a, b) 之间的总点数。它还允许 O(log n) 的插入和删除。我们将每个间隔的两个端点添加到它，并用它在 O(log n) 时间内计算 h。

计数交叉口

我们的其他数据结构与线段树非常相似，但有两个主要区别：我们不是从输入的区间集推断区间的起点和终点，而是将终点集取为介于 1 和n 包括在内，并且没有“开集”（这是为了简化以后添加新区间）；我们以特定方式存储每个节点的间隔集。

为简单起见，假设 n 是 2 的幂（如果不是，只需选择 2 的下一个最大幂——这将导致小于 n 的增加，因此时间复杂度不会改变）。令 T 是一棵完全二叉树，每个位置都有一个叶节点 1 <= i <= n。（这棵树总共有 2n - 1 个节点。）每个叶节点代表一个位置。每个非叶子节点代表其下所有叶子节点位置的并集，它必须形成一个长度为2的幂的区间。称该区间为节点v Int(v)。（注意：因为这个二叉树是完整的，它可以“隐式”表示，就像二叉堆通常一样，以节省空间。）

对于 T 的每个节点 v，都有一组称为 Span(v) 的区间。（我们实际上只存储它们最右边的端点。） Span(v) 是 D 中所有区间的集合，它

1. 包含 Int(v)，并且
2. 不包含 Int(parent(v))。

在每个顶点 v 中，我们仅将 Span(v) 中区间的最右边端点存储在按此端点排序 的自平衡二叉树中，其中每个节点都增加了后代节点的数量。也就是说，“外部”树的每个节点都包含一个“内部”树。 这对于使我们能够有效地计算有多少间隔完全包含给定的查询间隔是必要的。

段树上的基本查询操作是确定包含给定点 x 的区间集，这很容易更改为计数而不是报告单个区间。操作很简单：设置v为根，

1. 将 Span(v) 中的区间数加到总数中。
2. 如果 v 是叶子，则停止。
3. 否则，假设 v 的左右孩子分别是 u 和 w。如果 x 包含在 Int(u) 中，则在 u 上递归，否则在 w 上递归。

给定一个查询区间(a, b)，上述查询可以执行两次，一次针对a，一次针对b。将 nStraddlingAtLeastOne 设置为两个查询的计数之和。请注意，每个节点的计数可以在 O(1) 时间内完成——它只是存储 Span(v) 的自平衡二叉树的根节点的计数字段。

双重穿越！

困难（最终阻碍了我在 O(log n) 算法上的早期尝试，我花了一些时间）是我们还需要计算同时跨越查询的两个端点（a，b）的间隔数。为此，我们再次从根处的 v 开始，并对 a（查询的起点）执行修改后的查询，其中步骤 1 替换为：

1. 计算 Span(v) 中右端点 >= b 的区间数，并将其添加到总数中。

由于自平衡二叉树，这个计数步骤可以在 O(log n) 时间内执行。由于每个树级别最多需要 2 个这样的计数操作，这就是将时间复杂度推高到 O(log^2 n) 的部分。将 nContaining 设置为此查询的总数。我们可以使用计算 nStraddlingOne

nStraddlingOne = nStraddlingAtLeastOne - nContaining

使用 nStraddlingOne 和从 Fenwick 树计算的 h，我们现在可以根据顶部的等式计算 nContained。

添加和删​​除间隔

更新也是 O(log^2 n)，因为更新 Fenwick 树是 O(log n)，并且使用以下算法将区间 (x, y) 添加到段树需要 O(log^2 n) 时间，以 v 开头：

1. 如果 (x, y) 包含 Int(v)，则将 y 添加到存储 Span(v) 右端点的自平衡二叉树并停止。
2. 否则，假设 v 的左右孩子分别是 u 和 w。
   • 如果 (x, y) 与 Int(u) 重叠，则在 u 上递归。
   • 如果 (x, y) 与 Int(w) 重叠，则在 w 上递归。

上面的遍历只访问了segment树中的O(log n)个节点，因为每个添加的区间都会出现在任何树级别上最多2个节点的区间集中，每个区间最多使用2log(n)个空间。请参阅分段树上的 Wikipedia 页面以获取证明和进一步解释。删除间隔使用类似的算法。在节点处向自平衡二叉树中的每次插入或删除都需要 O(log n) 时间，总共需要 O(log^2 n) 时间。

空间使用

空间使用量为 O(nlog n)，因为段树中有 O(log n) 个树级别，每个级别可能需要空间用于包含每个可能端点的内部树节点的 2 个实例。特别注意，即使有 O(n^2) 个可能的不同区间，我们也只存储每个区间的最右边的端点，所以这不是问题。同样因为我们存储计数，添加现有间隔的第二个副本只会导致计数增加——它不会导致任何新的节点分配。Fenwick 树仅使用 O(n) 空间。

Answer 2

请参阅范围树。查询的时间复杂度为 O(log ^d n + k)。这里 d 是维度，n 是存储在树中的点数，k 是查询报告的点数。

但是我们只需要计数而不报告分数。所以我认为如果在每个节点上保持子节点的数量（实际上是叶子的数量，因为实际的点存储在叶子中），这个 k 可以被消除，留下 O(log ² n)。插入和删除也是 O(log ² n)。

Answer 3

一个区间树适合这里，例如https://github.com/ekg/intervaltree/blob/master/IntervalTree.h看到这个代码，它提供了一个 findContained 看起来 O(log(n))，除了删除是更复杂但肯定可以在 O(log(n)) http://en.wikipedia.org/wiki/Interval_tree#Deletion中完成

Answer 4

有时可以使用简单的排序集：
- 数据集中的区间有一些已知的最大长度，
- 另外，与集合中 x 个数据点的总值范围相比，这个最大长度并不太大。

在这种情况下，只使用简单的排序集就足够了：
- 仅使用间隔的 向它添加x dimension间隔。
- 像这样查询它：get intervals with their x dimension in range [x', y'] and then filter out the few intervals that have their y dimension crossing the y' limit。

给定上述关于具有已知最大长度的数据属性的相同前提条件，该逻辑可以扩展为也执行类似区间树的查询，其中查询不要求“纯粹包含在区间内的数据”，而是要求“数据重叠给定的间隔”。在这种情况下，查询将是：
- get intervals with their x dimension in range [x' - maximum interval range, y' + maximum interval range] and then filter out the few intervals that actually are outside of requested range。