範圍並集的長度

我需要在一維座標系中查找範圍並集的長度。我有很多範圍[a_i，b_i]，我需要找到這些範圍的聯合長度。範圍可以動態添加或刪除，可以在任何狀態下查詢範圍並集的長度。範圍並集的長度

例如：是範圍是：

[0-4] 
[3-6] 
[8-10]

輸出應該8.

是否有此目的的任何合適的數據結構與複雜以下上限：

Insertion - O(log N) 
Deletion - O(log N) 
Query - O(log N)

沒有，有沒有這樣的結構，將做到這一點，你必須自己編寫 –

@EugenHalca你是什麼意思，我當然會寫我自己，我只是查詢的名稱。 –

什麼會使輸出8？對於這個聯盟，我看到[0-6]，[8-10]。如果可能的值是0,1,2,3,4,5,6和8,9,10，則總數爲10. –

一時間，假設你有一個排序的數組，同時包含起點和終點，與起點之前的終點與同一座標的慣例。與您的示例中，陣列將包含

0:start, 3:start, 4:end, 6:end, 8:start, 10:end

（如果有在3結束的時間間隔，然後3:start將先3:end）

要執行的查詢時，執行掃描從左至右，遞增一個在「開始」計數器和在「結束」遞減一個計數器。您記錄爲S計數器從0增加的位置，並記錄爲 E計數器變爲零的位置。此時，您需要在總數中加上S和E之間的元素數。這也是一個重點，你可以用區間[S, E]替換前面的區間。

現在，如果需要O（log n）的用於插入/缺失的複雜性，而不是在陣列中，則存儲元件相同的元件（對座標和開始或結束標誌）在平衡二叉樹。然後根據inorder遍歷執行掃描。

查詢本身保持O（n）的複雜性。

2013-12-12 22:08:32 chill

您仍然可以使用數組並使用二進制搜索來插入/刪除O（log n）。 – justhalf

而我的猜測是，查詢的下界是Ω（n）。考慮覆蓋其他區間範圍的單個區間的情況。當你刪除這個間隔時，我想你需要檢查一切。但這只是一個想法。 =） – justhalf

我想我能得到的最好是O（n）查詢。我嘗試了一些其他的數據結構，它將範圍存儲爲樹的節點（樹葉），插入和刪除是O（log N），但在最壞的情況下查詢是O（n）。 –

這不完全是O(lg n)，而是interval tree或segment tree是否符合您的需求？你可以保持聯盟的長度在一個變量，並插入或取出的時間間隔時，您可以在O(lg n + m)時間什麼其他米間隔交叉處找到，然後利用這些信息在O(m)及時更新長度是可變的。

2013-12-12 21:59:10

保持頻率陣列。例如：如果你的範圍是（0,2）和（1,3），你的頻率數組應該是[1,2,2,1]。還要保持頻率數組中非零元素的計數。

爲了插入，增加對應於該範圍內的頻率。當你從0增加到1（但不是從1到2等）時更新計數。

對於刪除，減少頻率。同樣更新計數。

用於查詢，輸出計數。

複雜性是範圍的長度。

2013-12-13 06:12:06 ElKamina

回答