我想知道是否有一种数据结构能有效地处理以下情况:
该数据结构应存储一些可能重叠的可变长度范围,这些范围在某个连续时间尺度上。
例如,您可以添加范围
a:[0,3], b:[4,7], c:[0,9]
。插入时间不需要特别高效。
检索将使用范围作为参数,并返回集合中与该范围重叠的所有范围,例如:
Get(1,2)
将返回 a 和 c。Get(6,7)
将返回 b 和 c。Get(2,6)
将返回所有三个。检索需要尽可能高效。
我想知道是否有一种数据结构能有效地处理以下情况:
该数据结构应存储一些可能重叠的可变长度范围,这些范围在某个连续时间尺度上。
例如,您可以添加范围 a:[0,3], b:[4,7], c:[0,9]
。
插入时间不需要特别高效。
检索将使用范围作为参数,并返回集合中与该范围重叠的所有范围,例如:
Get(1,2)
将返回 a 和 c。 Get(6,7)
将返回 b 和 c。 Get(2,6)
将返回所有三个。
检索需要尽可能高效。
您可以使用的一种数据结构是一维 R-tree。 这些数据结构旨在处理范围并提供高效的检索。 您还将了解 Allen's Operators;除了“重叠”之外,时间间隔之间还有其他十几种关系。
还有其他与此领域相关的SO问题,包括: