一維空間索引的數據結構

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（日誌N）。

從很好理解的標準數據結構是否有很好的適應性？

Answer 1

一種interval tree想到，它是：（維基百科的描述中，從here圖像）

與每個節點存儲樹：

• 中心點
• 一個指針，指向另一個節點包含完全在中心點左側的所有間隔
• 指向另一個節點的指針，該節點包含完全與ri相關的所有間隔中心點GHT
• 所有間隔重疊而他們的開始點排序的中心點
• 所有間隔重疊的中心點通過他們的終點分類

它允許O(log n + m)區間相交查詢，其中m是相交區間的數量。

您必須查看任一站點以瞭解有關構造和查詢的更多詳細信息。