问题标签 [interval-tree]

我正在使用R 上的这些数据。这些是前六行——不包括 write.csv 函数总是添加的第一列——：

每行代表不同的合同。变量inter_complex是一个复数，其实部是合约开始日期的数字表示，而其虚部类似地表示合约结束日期。如果您想知道，您可以通过执行以下操作来获取该列：

我想要的是，对于每个客户 ID 和每个合同，确定有多少与同一客户 ID 关联的合同与该合同相交。换句话说：我想创建一个名为同时的新列，它将为每一行（即每个合约）描述在当前合约处于活动状态的同一时期相应客户有多少活动合约。如果没有为给定合约找到与任何其他合约的交集，则同时的值必须为 1——因为当该合约处于活动状态时，它也是相应客户拥有的唯一活动合约——。

我认为这将有助于获得inter_complex的组合，然后将这些复数组合转换为区间组合，然后使用 lubridate 的 intersect 函数来辨别每个区间组合是否相交。为此，我编写了以下代码：

为了更好地掌握 get_intersections 函数的作用，我建议您运行以下命令：

数据框显示了间隔对之间example[[1]]是否存在截取——或者，更准确地说，是重叠。数据框example[[2]]显示三个区间的组之间是否存在重叠，等等。

您可能会注意到，根据example[[1]]间隔2019-07-15 UTC--2020-07-15 UTC与其他一些间隔重叠——因此，同时的关联值为2——而根据变量同时example[[2]]的值为 3 。自然地，这个想法是为每个间隔分配其最高的同时值。

由于我不关心全局重叠，而是关心每个客户端 ID 内的重叠，我认为我需要处理分组数据框。我在这个项目上得到的最远的是写这个：

现在谈谈我的问题。1）我已经执行了上面的行，但是这个过程效率不是很高。它已经运行了一整天多一点，但还没有完成。最近我遇到了区间树的概念，但我不是计算机科学家，我需要帮助才能以更智能的方式解决这个问题。2）如果我们坚持我不太聪明的方法来解决这个问题，我仍然需要一个函数来访问由get_intersections返回的列表的每个元素，以便识别和检索与每个元素关联的最高同时值间隔。在这件事上，我也不得不请求帮助。

编辑

关于 Wimpel 的回答，我检查了他们的数据表并发现了这一点。

也就是说，显示的合同据称与同一客户的其他七份合同重叠。

另一方面，让我们看看在使用我的基于组合的方法时这是否成立。

相同的合约显示在上面小标题的第一行。可以看出，该合同实际上与给定客户的其他九个合同重叠——这九个显示在剩余的行上——。

我不知道 Wimpel 的解决方案是如何出错的，但我检查了它确实为其他几个合同提供了正确的交叉点数量。现在我知道我正在寻找基于数据表的解决方案，因为流程非常快，但建议的解决方案似乎存在问题。

给定一个数组 a[]有n 个非负元素。我们有两种类型的查询：

A xyv : 找到 a[i]>v 的第一个索引 i (x<=i<=y)

B uv :更新a[u]=v;

我使用分段树，但在某些测试中它是 TLE。

这是我的代码。

这是构建第一棵树的函数。

更新查询：

“查找”查询：

我正在尝试从一些样板红黑树代码中创建一个间隔树。要制作支持间隔的增强红黑树（如 Wikipedia 中所述），您需要对其进行增强以存储任何子节点的任何范围的最大值。我了解如何在插入时注释每个节点，因为它是一个简单的比较和更新，但是由于如何正确处理旋转，我被卡住了。（至少我认为这是我的问题）

所有的教程和视频都像是挥手说“更新旋转注释”。任何提示、资源或代码（伪或其他）来查看如何完成插入/删除和增强？

考虑以下程序：

输出是

问题：

• 为什么最后一行是2？
• 区间图是不是应该把值加起来，所以它是 5？
• 如何实现添加间隔并+=保留值的行为？

我想要以下结果：

也就是说，当添加间隔时，它们被合并，并且组合值被存储用于整个合并的间隔。

此操作可能没有数学意义，但这是我在程序中需要的。（另外，我不减去间隔）。