0

我有一个区间数组 [a,b](其中 [a,b] = 所有 x 的集合,使得 a<=x<=b)。这些间隔中的每一个都有一个与之关联的值(将其视为跨该间隔的某物的成本)。间隔可以重叠。间隔是动态的(可以添加、删除、转换它们,并且可以更改它们的大小)。此外,与任何此类间隔相关的值可能会发生变化。

我需要创建一个图表,其中包含跨区间 [start, end] 的所有此类值的总和,该区间被定义为包含所有此类区间的区间。为了做到这一点,我需要一个有序列表,列出这些值在哪里发生变化,以及它们在哪些值之间变化。当原始数组中的间隔发生变化时,需要轻松/快速地更新此类列表。

旁注:假设间隔不是很大(数百个?)。

有关有效执行此操作的数据结构/算法的任何建议?

4

1 回答 1

0

区间树能够执行这样的操作

于 2012-04-05T11:42:10.940 回答