问题标签 [interval-tree]

我有一个带有整数值的区间列表[例如。[1, 4], [10, 19] 等]。有没有办法将这些间隔放入一些 java 集合的容器中 [例如。设置] 这样我就可以在容器上调用“联合”函数。“联合”函数应该给我一个间隔列表，这样如果任何 2 个插入的间隔重叠，那么它们应该合并到输出中。我尝试在 Guava 中使用 Range 类，但最终在合并之前将所有间隔相互比较。对此的优雅方法将不胜感激！这是我根据下面的回复尝试过的。输出为 [[1, 15], [17, 20]]，正确。我想知道是否有一些现有的 API 实现了这样的东西。

谢谢

我正在使用 Guava 的 Range 类来处理间隔。我想知道是否可以通过使用一些番石榴的收集容器找到从一组间隔到给定点/间隔的最近间隔？

我尝试在 Java 中搜索区间树，这就是我找到的。如果可能的话，我宁愿通过使用 Guava 类之一来做到这一点。

http://picard.sourceforge.net/javadoc/net/sf/picard/util/IntervalTree.html http://tribble.googlecode.com/svn/trunk/src/org/broad/tribble/index/interval/IntervalTree .java

谢谢

我正在尝试在 python 中实现一个段树类。段树允许在对数时间内查询范围（更多关于段树）。在我的实现中，我持有必要的信息，以便能够回答 range 中元素的总和(i, j)。下面是我的代码。由于我是 python 新手，我仍然在每行末尾使用分号（继承自 C++）。

构建函数应该从输入数组构建段树a。当我运行程序时，我得到以下输出：

我不明白为什么序列的所有值都24在build函数退出之后。build调试信息在函数运行时显示了许多其他值，但在它退出后，所有值都神奇地变成了24. 为什么会这样？提前致谢。

我已经按照 CLRS 算法书中的概述在 Java 中实现了一个区间树（它使用红黑树作为底层结构）。在书中（据我在网上看到的），它讨论了如何找到其区间包含被查询数字的节点。

在我的情况下，如果被查询的数字不属于任何区间，我想知道“最近”节点是什么，即那些区间位于查询之前和之后的节点。我已经使用以下函数完成了这项工作。每个节点都包含区间（int low, int high），以及它们自己及其子树的最小值和最大值。

当然，问题在于函数 findPrev() 和 findNext() 都遍历整个树并且没有利用树的结构。有没有办法在 O(lgn) 时间内执行此查询？

我还考虑了创建第二个包含所有间隔间隙的间隔树的可能性，并在那里简单地进行查询。然后，节点将包含有关哪些元素在该间隙之前和之后的信息（我已经尝试过，但到目前为止还没有成功实现这一点）。

编辑：请注意，函数 findPrevNext() 在尝试查找查询失败后被调用。因此，已知查询不会事先落在任何给定的时间间隔内。

在 CLRS 第 2 版，第 4 次印刷，第 288-9 页之后，我正在为区间树实现红黑树删除。

错误总结：

RB-删除-修复

如果 x 和 w 是标记节点，这是 RB-Delete 的可能结果，则分别评估 color(left(w))。RB-Delete-Fixup 中的 color(right(w)) 在 while 循环的第一次迭代中遇到空指针异常。

这个问题的所有代码都在 Clojure 中：

https://github.com/mobiusinversion/interval-trees

这是抛出异常时的红黑树状态图：

http://gorillamatrix.com/files/rb-delete-fixup.jpg

失败的单元测试是

在文件中

以下是 lein test 的输出：

问题似乎是在分配之后

CLRS, pg. 289 rb-delete-fixup 伪代码第7行，w指向sentinel节点，因此伪代码第9行没有左右检查颜色。

Clojure 实现中抛出异常的行在这里

勘误表中似乎没有提交错误：

http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php

我很抱歉这个问题非常具体和密集，但非常感谢您的帮助，我已经为此苦苦思索了好几天。

看来这个人问了同样的问题，但没有得到答案 红黑树删除算法

更新：我在第三版第三版中实现了delete和delete fixups例程，但未能解决问题。

段树、区间树、二叉索引树和范围树在以下方面有什么区别：

• 关键思想/定义
• 应用
• 更高维度的性能/订单/空间消耗

请不要只给出定义。

我需要将一些间隔（实际上这些是地址间隔）映射到对象 ID。

我尝试使用boost的interval_map，这个例子看起来很漂亮，它很容易枚举所有的间隔，比如：

哪个输出：

但它不能做这样的事情：

它输出：error: no match for 'operator[]' in 'party[when]' 它看起来很奇怪，因为 map 的主要功能在 operator[]

所以我无法获得“在特定时间参加聚会的人”的信息

这个问题有现成的解决方案吗？

这与寻找重叠区间有关。我知道如何在给出区间列表（区间树）的情况下这样做。我所拥有的是间隔列表。例如，

结果应该是

[2,3], [7,8]

我需要做的是找到所有列表中通用的间隔列表。

我认为这个问题类似于合并n列表。问题是我不能应用列表的成对合并。应用此方法可能会导致重叠间隔丢失。所以我需要一次将所有列表合并在一起（而不是成对的）。

我可以使用区间树。将每个列表中的第一个间隔插入到间隔树中并找到重叠。从树中删除最弱的区间并从其中一个列表中插入下一个区间。我还没有完全弄清楚如何使用这种方法，但似乎它会变得太贵。

是否有任何有效的算法可以从间隔列表中查找重叠间隔。？

附加信息： 列表中的间隔已排序。它们不重叠并形成一个序列。

所以，我可能应该先解释一下我想如何实现它。我的想法很简单，我想创建每个块并通过利用每个块本地的浮点网格来确定每个顶点的位置，然后我想将体素放置在一个大的 64 位整数网格中（每个块的位置由它具有的整数值，0,0,0 将是中间，20,20,20 将在 x、y 和 z 轴上 20 个块）进一步创建一个巨大的世界我会进行一些检查以确定如何将根据它们在整数网格中的位置推断出块，这是我尚未弄清楚的。（不如让它运行重要）

我遇到的问题：

1. 弄清楚如何使用 libnoise 生成 3D perlin 噪声，据我所知，该文档没有涉及这个主题，而且我从谷歌那里得到了没有像样的结果。
2. 不知何故将块放在整数网格中
3. 弄清楚一个人将如何确定从网格中的位置推断出该块的坚固程度（我认为这很简单，例如检查周围的块是什么以及您在网格中的位置并根据该数据确定它）
4. 根据从整数网格推断出的位置，将各种稀有矿石散布在周围，这相当容易，但在解决其他问题之前无法完成。
5. 找出区间树。

那么，有什么想法吗？到目前为止的相关代码（删除了光、遮挡、UV 和正常计算代码，因为它与问题无关）

据我所知，你可能会注意到这段代码与用 C 和 python 编写的某个演示非常相似，这是因为很多代码是在阅读后编写的，对我来说有点影响

问题是它似乎没有涵盖我的问题，它让我对体素的工作方式有了更好的理解，就是这样。

那么，关于我应该如何解决我的这个项目的任何指示？

PS，这和战地 3 是 DOOM 克隆一样多是我的世界克隆，我想我会让你决定如何解释。

哦，我已经完成了我的研究，我发现：关于 0fps 的帖子，我相信你们中的大多数人都熟悉博客 https://sites.google.com/site/letsmakeavoxelengine 和其他一些，包括 GPU gems 3，行进立方体和其他一些东西，没有一个能解决我的问题。

我正在尝试确定一种合适的方式来完成以下任务。

我想要范围 - >在特定范围内设置查找（比如[0x0 - 0xffffffff]）。值被插入到范围内（所以如果我们使用 T = 唯一字符串），我可能会 insert("beef3490", [0x1234, 0xFFFF]); 并且单个 id 可能有多个插入，它们可能重叠也可能不重叠。此外，可能会插入其他重叠的值，并且它们重叠的地方我应该收到一组唯一字符串作为结果。最后，值也可以从范围中删除（不一定匹配，但通常包含在它们的初始插入范围内）。

这是一个简化的示例用法：

这给我带来了一些问题：

1. 是否有此类问题的通用名称，或者我可以从中找到见解的类似类型的问题？

2. 考虑到以下限制，理想的实现是什么：

   • 快速/非常快的查找时间
   • 内存使用不会膨胀（即以下操作具有等效的占用空间）
   • • 插入[10,20]，插入[20,30]，删除[14,24]
   • • 插入[10,15]，插入[25,30]
   • 与上一个类似，数据结构在长时间运行的系统上应该具有稳定性
   • 插入/删除时间并不是绝对可怕的（尽管它们不需要像查找一样快）

3. 给定一个理想的实现，您对在 C++ 中使用它有什么建议吗？

感谢所有回复和帮助。