问题标签 [interval-tree]

我正在阅读Cormen 的《算法导论》第 14 章（增强数据结构），他在其中谈到了区间树。下面是他提到的区间树背后的设计方法。

第一步：底层数据结构

我们选择一棵红黑树，其中每个节点x包含一个区间x:int ， x的键是该区间的低端点 x.int.low。因此，数据结构的中序树遍历按低端点排序的顺序列出了区间。

这可以通过声明一个具有min和max的节点来完成。compareTo函数应该只比较x.int.low。

Step 2: Additional information

In addition to the intervals themselves, each node x contains a value x.max, which is the maximum value of any interval endpoint stored in the sub-tree rooted at x.

Step 3: Maintaining the information

We must verify that insertion and deletion take O(lg n) time on an interval tree of n nodes. We can determine x.max given interval x.int and the max values of node x’s children:

x:max = max(x.int.high; x.left.max; x.right.max)

Step 4: Developing new operations

The only new operation we need is INTERVAL-SEARCH(T,i), which finds a node in tree T whose interval overlaps interval i. If there is no interval that overlaps i in the tree, the procedure returns a pointer to the sentinel T:nil.

I can implement this by AVL tree but out of curiosity want to know whether we can augment existing libraries in java like TreeSet or other collection entity to fit to above design. If so, can you please help in a sample code or example?

给定一个时间间隔列表，我需要找到一组最大非重叠间隔。

例如，

如果我们有以下间隔：

还规定时间必须在范围内[0000, 2400]。

最大不重叠的间隔集是[0600, 0830], [0900, 1130], [1230, 1400]。

我知道最大集装箱是 NP-Complete 的。我想确认我的问题（间隔仅包含开始和结束时间）是否也是 NP-Complete。

如果是这样，有没有办法在指数时间内找到最佳解决方案，但需要更智能的预处理和修剪数据。或者如果有一个相对容易实现的固定参数易处理算法。我不想使用近似算法。

我有数百万个包含以下字段的文档：
名称（字符串）、开始版本（int）、结束版本（int）。

我需要有效地查询所有回答查询的记录：
选择 version >= "start version" and version<="end version" 的所有文档

运行上述查询需要 50-100 毫秒，而通过标记每个版本的类似查询只需要 15 毫秒。

我的问题是 Solr 处理此类查询的效率如何？
欢迎任何替代解决方案。
如果需要，可以更改字段值/类型。

给定一组 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) 整体解决方案？

编辑：我制定的伪代码：

我正在尝试将间隔列表划分为不重叠的子间隔。例如，如果我的输入是

我希望输出是

我希望输出是一个间隔列表，它与原始间隔列表具有相同的联合，但是多个不同子间隔的每个重叠子间隔都被制成不同的间隔。

我的第一个想法是我应该按它们的第一个元素对所有间隔进行排序，如果有重叠，我应该创建一个新的间隔，但是我在让它工作时遇到了一些麻烦。这在本质上似乎与许多间隔问题不同，所以任何建议都会很棒！

这就是问题所在，这里有一个解决方案。

第一部分很简单。这是我没有得到的第二部分，无论我多么努力。你基本上有两组区间，需要找到一个区间不完全在另一个区间内的所有交叉点。

我一直盯着问题设置器代码，直到我的眼睛开始流血。仍然无法理解这一点：

它是如何工作的？算法是什么？

社论中指出，您可以使用区间树或“二进制索引树”来解决此问题。我或多或少地了解什么是区间树以及它如何有用。但是问题设置者显然没有使用它，并且“二进制索引树”没有出现在搜索中，而是有“二进制索引树”，它处理部分总和，我看不出它是如何相关的（它可能非常好吧，它是相关的，但我不明白如何）。

有什么帮助吗？指向我需要阅读的文学作品？

我有一组重叠的间隔，我必须从相应的间隔中选择一个元素，这样当它们被分组时，选择中的间隔最小。

分组我的意思是连续的元素被分组。如果一个元素没有来自其他区间的连续元素，则将其视为具有一个元素的组

通过最小化差距，我的意思是，我们减少了此类群体的数量并尝试形成更大的群体

我看到了区间树，并认为这可能会有所帮助，但不确定如何为我的利益使用它

请告诉我应该采取什么方法来解决问题。

例子：

间隔（包括边界）

可能的解决方案

通过选择上述元素组成的组

所以只有一个差距 4 到 9

我有一个间隔列表，我需要返回与查询中传递的间隔重叠的那些。特殊之处在于，在典型查询中，大约三分之一甚至一半的间隔将与查询中给出的间隔重叠。此外，最短间隔与最长间隔的比例不超过 1:5。我实现了自己的区间树（增强的红黑树）——我不想使用现有的实现，因为我需要对闭区间和一些特殊功能的支持。我用 6000 个间隔的树中的 6000 个查询测试了查询速度（因此 n=6000 和 m=3000（应用程序））。事实证明，蛮力和使用树一样好：

让我使用渐近分析。n：查询次数；n：间隔数；应用程序。n/2：查询中返回的间隔数：

时间复杂度蛮力：n*n

时间复杂度树：n*(log(n)+n/2) --> 1/2 n n + n log(n) --> n*n

所以结果是说对于大的n，两者应该大致相同。考虑到 n*n 前面的常数 1/2，仍然有人会以某种方式期望树明显更快。因此，对于我得到的结果，我可以想象三个可能的原因：

a）我的实施是错误的。（我应该像下面那样使用 BFS 吗？） b）我的实现是正确的，但是我让 Python 的事情变得很麻烦，所以它需要更多的时间来处理树而不是处理蛮力。c) 一切正常 - 这就是大型 n 的行为方式

我的查询函数如下所示：

我像这样构建树：

编辑：

一个节点表示如下：

子树中的所有节点都可以这样获取：

ps 请注意，通过利用存在如此多的重叠并且所有间隔都有相当的长度，我设法实现了一种基于排序和二等分的简单方法，该方法在 80 秒内完成，但我会说这是过度拟合...... ，通过渐近分析，我发现它应该有app。与使用树相同的运行时...

我有一个带有两个整数列 START 和 END 的 pandas 数据帧 INT，表示间隔 [START，END]。我需要检查整数 POS 是否落在这些间隔之一中，即是否存在 START <= POS <= END 的行。我需要为数十万个 POS 执行此操作，并且我有数千个间隔。一切都已排序，包括间隔和 POS 值。

我有我认为是一个有效的解决方案，按顺序检查 POS 值并跟踪最后最近的间隔，这样我就可以开始有希望地接近我想要的间隔（如果存在的话），我只需要继续前进检查是否有间隔表：

然而，这比我想要的要慢，因为它是在纯 python 中，有没有一种有效的方法可以在 pandas 或 numpy 中做到这一点？

我已经尝试过类似的东西

但这比我的解决方案慢得多。有什么建议吗？我错过了图书馆功能吗？

谢谢

编辑：也许我应该提到我需要检查一个（排序的）POS 值系列，我目前正在使用positions.map(find)它来生成一个布尔系列，也许有更好的方法可以做到这一点。此外，我必须为数千个位置和间隔执行此操作，这就是我对速度感兴趣的原因。

我有一个关于区间树的问题要解决，并且我基本上知道算法，但是当我的函数将值返回给它的主要值时，我的代码中有问题。

我遇到的问题是找到某些索引之间的最大值，并更新数组中的某些值。所以有一个具有 n 个数字和 m 个操作的初始数组。如果操作从 0 开始，我应该对 index 之间的最大值进行询问x。x如果操作从 1 开始，我应该用 更新初始向量上的索引值y。

问题是，在某些询问中，它会在文件中检索正确答案，而在某些情况下，它只是给出一些“随机”数字。

我在代码期间做了一些 printf 以便我可以监视答案，我看到最后，在函数中，在返回值之前它是完全正确的，当我在函数之后立即在 main 中检查它时，它给了我结果我告诉你了。

这是我正在测试的输入：

代码：

对不起，很长的帖子和很长的代码，如果我遗漏了什么，请提醒我。

先感谢您！