表示分段連續範圍的數據結構？

Question

假設我有一個長度爲400的整數索引數組，並且我想從頭開始丟棄一些元素，從最後開始丟棄一些元素，並且也從中間刪除一些元素，但實際上並未改變原始數組。也就是說，而不是通過使用指數{0...399}，我想用一個分段連續範圍的陣列循環如

{3...15} ∪ {18...243} ∪ {250...301} ∪ {305...310} 

什麼是一個很好的數據結構來描述這種指數範​​圍？一個顯而易見的解決方案是創建另一個「索引介體」數組，其中包含從連續零基索引到上述新座標的映射，但是這樣做感覺很浪費，因爲幾乎所有元素都只是連續數字，只是偶爾「跳躍」。此外，如果我發現，噢，我想修改一下範圍？整個索引數組必須重新構建。不太好。

有幾點需要注意：

• 的範圍從來沒有重疊。如果新的範圍添加到數據結構中，並且與現有範圍重疊，則整個事件應該合併。也就是說，如果我在上面的示例中添加範圍{300... 308}，則應該用{250...310}替代最後兩個範圍。
• 應該在整個範圍是相當便宜的只需循環。
• 直接查詢值也應該比較便宜：「給我對應於映射座標中第42個索引的原始索引」。
• 它應該是可能的（雖然也許不是很便宜），以全面工作的其他方法：「給我映射座標對應42的原始座標，或者如果它映射在所有的人說。」

在滾動我自己的解決方案之前，我想知道是否存在一個衆所周知的數據結構，可以優雅地解決這類問題。

謝謝！

Answer 1

好像整數對的數組或列表將是最好的數據結構。您可以選擇該對的第二個整數是終點還是來自第一個整數的計數。

編輯：在進一步的反思，這到底是什麼問題數據庫索引必須做。如果整數對不必按數字順序排列，則可以更輕鬆地處理分割。如果數字序列必須保持有序，則需要一個數據結構，允許您將整數對添加到數組或列表的中間。

的分割將具有與（6，12）的整數對改變爲（6,9）（11，12）中，當10被去除，作爲一個例子。

此外，如果我發現，如果我想修改範圍有點呢？整個索引數組必須重新構建。不太好。

真。也許一個整數對需要改變。最糟糕的情況是，你必須重建整個數組或列表。