用于处理闭合间隔的数据结构

Question

我在为考试学习时发现了我无法处理的问题：

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

插入（x，y）-添加间隔[x，y]

移除（x，y）-移除间隔[x，y]

Count（x，y）-计算纯粹包含在区间内的区间数[x，y]

x、 y是从1到n的整数。所有操作最多需要O（（log n）^2）

有人能帮忙吗？

Answer 1

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

Answer 2

请参见范围树。查询的时间复杂度被称为O（log^dn k）。这里d是维度，n是存储在树中的点数，k是查询报告的点数。

但我们只需要计数，不需要报告点数。所以我认为，如果在每个节点上保持子节点的数量（实际上是叶子的数量，因为实数点存储在叶子中），那么可以消除k，留下O（log^{2n）。插入和删除也是O（log2n）。}

Answer 3

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

该算法基于对给定查询范围（a， b）的观察，

n包含=（h-nStraddlingOne）/2

其中，nContain是（a， b）包含的间隔数，h是（a， b）中任何一种（开始或结束）的间隔endpoint数，nStraddlingOne是仅包含a或仅包含b的间隔数。任何时间间隔的“数据库”在这里称为D。

Fenwick树允许您使用O（n）表计算O（log n）时间内两个整数索引（A，b）之间的总点数。它还允许O（log n）插入和删除。我们将每个间隔的两个endpoint添加到它，并使用它来计算O（log n）时间中的h。

我们的另一个数据结构非常类似于段树，但有两个主要区别：不是从输入的区间集推断区间的起点和终点，而是将endpoint集取为1到n（包括1到n）之间的所有可能整数，并且没有“开放集”（这是为了简化以后添加新区间的过程）；我们以特定的方式存储每个节点的间隔集。

为简单起见，假设n是2的幂（如果不是，只需选择下一个最大的2的幂——这将导致小于n的增加，因此时间复杂度不会改变）。设T是一个完整的二叉树，每个位置1有一个叶节点

对于T的每个节点v，都对应着一组称为Span（v）的间隔。（我们只会实际存储它们最右边的endpoint。）Span（v）是D中所有间隔的集合

1. 包含Int（v）和

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

段树上的基本查询操作是确定包含给定点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）算法的原因）是我们还需要计算同时跨越查询的两个endpoint（a， b）的间隔数。为此，我们再次从根处的v开始，并对a（查询的起点）执行修改后的查询，其中步骤1替换为：

1. 计算具有右endpoint的跨度（v）中的间隔数

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

nStraddlingOne=nStraddlingAtLeastOne-n包含

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

更新也是O（log^2 n），因为更新Fenwick树是O（log n），并且使用以下算法将间隔（x，y）添加到段树需要O（log^2 n）时间，从根处的v开始：

• 如果（x，y）包含Int（v），则将y添加到存储Span（v）和stop的右endpoint的自平衡二叉树中

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

空间使用率为O（nlog n），因为段树中有O（log n）树级别，每个级别可能需要空间来容纳包含每个可能endpoint的内部树节点的2个实例。特别要注意的是，尽管有O（n^2）个可能的不同区间，但我们只存储每个区间的最右endpoint，因此这不是问题。此外，由于我们存储计数，添加现有间隔的第二个副本只会导致计数增加，而不会导致任何新的节点分配。芬威克树只使用O（n）空间。