data-structures - 一维空间索引的数据结构

Question

我有大量对象，每个对象代表一个数字范围(例如 [1,3]、[2,8]、[3,3])。我希望能够快速查询与给定范围重叠的所有范围。这是标准 2D 或 3D 空间索引(例如 R 树)的一维等效项。

例如:

Data = [0,1], [1,3], [2,8], [3,3], [5,9]
Query = [2,4]
Output = [1,3], [2,8], [3,3]

我想向结构中添加项目或从中删除项目，通常运行时间为 O(log N)，并且搜索结构通常也为 O(log N)。

是否有一个很好的适合易于理解的标准数据结构？

Answer 1

安interval tree我想到的是:(来自维基百科的描述，图片来自here)

A tree with each node storing:

• A center point
• A pointer to another node containing all intervals completely to the left of the center point
• A pointer to another node containing all intervals completely to the right of the center point
• All intervals overlapping the center point sorted by their beginning point
• All intervals overlapping the center point sorted by their ending point

它允许O(log n + m) 间隔相交查询，其中m 是相交间隔的数量。

您必须查看这两个网站以获取有关构建和查询的更多详细信息。