範囲のリスト内のポイントを見つけるためのどのようなデータ構造ですか？

Question

私はこのユースケースの正しいデータ構造を見つけようとしていますが、検索のための正しい用語がないようです。 Itemで表さ

struct Item { 
    var start: Int 
    var end: Int 
    var type: Int 
} 

範囲が重複しないと連続している：

は、私は次のような構造の多くのコピーを持っています。

私のことができるようにする必要があります：Itemが与えられたIntインデックス

ウォーク前方/後方位置Item

からItem意志の集合体である

• クエリ完全に再ビルドするか、最後に追加して定期的に更新する必要があります。ミッドコレクション挿入物は、ゼロからの再構築を保証するほど稀である。

  誰でも私に適切な構造を指摘してもいいか、おそらく正しい用語を自分自身の研究を続けることができますか？

Answer 1

項目が重複せず連続している場合は、終了は必要ありません（次の開始時に暗示されています）。ソートされたデータに使用する任意のデータ構造を使用できます。木やリスト。

一般的なケース（=オーバーラップ）では、おそらくinterval treeを使用します。