处理封闭间隔的数据结构

Question

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

设计一个处理(关闭)间隔的数据结构,它将提供三种操作:

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

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

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

x,y是从1到n的整数.所有操作最多可以占用O((log n)²)

有人可以帮忙吗？

Answer 1

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

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

nContained = (h - nStraddlingOne) / 2

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

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

计数路口

我们的其他数据结构与线段树非常相似，但有两个主要区别：我们不是从输入的区间集合中推断区间的起点和终点，而是将端点集合取为 1 到 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 上递归。

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

空间使用

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

Answer 2

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