"循环"区间树算法

Question

我想知道是否有人实现/了解处理循环区间的（最好是javascript）间隔树算法。在这里，循环意味着起始值 > 终止值。请注意，这也需要对区间大小进行限制。

这只是常见区间树问题的一个子问题吗？

回答评论中提出的问题：

下面是一个图像（感谢G. Bach和维基百科），说明了圆形子范围的含义： 以下是一些范围的json表示示例（与上面的图片无关）： [{id: 'range1', start: 3, end: 34}, {id: 'range2circular', start: 30, end:6}]

谢谢！

- tnrich

---

请提供一些示例。 - Nina Scholz

如果一个区间的长度为负数，你可以简单地将每个区间反转，因此如果一个区间是 (start, end) 且 start > end，则存储 (end, start, R)，其中 R 表示该区间已被反转。然后，您可以使用普通的区间树，并从 R 中知道给定结果的起始和结束已被反转。 - Dan D.

你的值来自哪个域？它们如何包装？ - Bergi

@DanD：不完全是，因为您还需要反转搜索。 - Bergi

我没有看到"循环"限定符和范围反转"起始 > 结尾"之间的逻辑联系。我认为你没有告诉我们正确的事情。 - user1196549

Answer 1

这与圆弧图形背后的思想相关（但不是图形本身，因为您从间隔开始，不关心它们的圆弧图形表示）。

假设这就是它的含义，那么域可以用类似于圆的度数的周期来表示。然后你有一个最小可能值min和一个最大可能值max = min + 1 * period，第一件事情是找到最小的s，使得start = min + s + k * period对于整数k（基本上，这是一个模操作），同样地，你找到最小的e，使得end = min + e + j * period。

现在你可以将区间表示为(s，e)，其中s > e。将其分成两个区间(s，max)和(min，e)，将它们放入区间树中，并为它们都提供对原始区间(start，end)的引用。如果你开始有可能重叠一个时间段的n个区间，则最终在树中会有2n个区间，并且渐近界限保持不变。

- G. Bach