[解決済み】セグメントツリー、インターバルツリー、バイナリーインデックスツリー、レンジツリーの違いは何ですか？

質問

セグメントツリー、インターバルツリー、バイナリーインデックスツリー、レンジツリーの違いは何ですか。

• キーアイデア/定義
• 用途
• 性能/高次元でのオーダー/消費スペース

定義だけを述べるのはやめてください。

どのように解決するのですか？

これらのデータ構造はすべて、さまざまな問題を解決するために使用されます。

• セグメントツリー は間隔を格納し、"に最適化されています。 どの区間が与えられた点を含むか クエリ。
• インターバルツリー はインターバルも格納しますが、" に最適化されています。 どの区間が与えられた区間と重なるか クエリ。また、セグメントツリーと同様に、ポイントクエリにも使用することができます。
• レンジツリー はポイントを格納し、" に最適化されています。 どの点が与えられた区間に含まれるか クエリ。
• バイナリインデックス付きツリー は、インデックスごとにアイテム数を格納し、" に最適化されています。 インデックスmとnの間にいくつの項目があるか クエリ。

1次元でのパフォーマンス/消費スペース。

• セグメントツリー - 前処理時間O(n logn)、問い合わせ時間O(k+logn)、空間O(n logn)
• 区間木 - 前処理時間O(n logn)、問い合わせ時間O(k+logn)、空間O(n)
• レンジツリー - 前処理時間O(n logn)、問い合わせ時間O(k+logn)、空間O(n)
• バイナリ索引木 - 前処理時間O(n logn)、問い合わせ時間O(logn)、空間O(n)

(kは報告された結果の数)。

すべてのデータ構造は、使用シナリオにデータの変更とクエリの両方が含まれるという意味で、動的であることが可能である。

• セグメントツリー - の区間を O(logn) 時間で追加/削除することができます ( こちら )
• インターバルツリー - 区間はO(logn)時間で追加/削除できる
• レンジツリー - 新しい点は O(logn) 時間で追加/削除できます ( こちら )
• バイナリ索引ツリー - インデックスごとのアイテム数をO(logn)時間で増やすことができる。

高次元(d>1)の場合。

• セグメントツリー - 前処理時間O(n(logn)^d)、問い合わせ時間O(k+(logn)^d)、空間O(n(logn)^(d-1))
• 区間木 - 前処理時間O(n logn)、問い合わせ時間O(k+(logn)^d)、空間O(n logn)
• レンジツリー - 前処理時間O(n(logn)^d)、問い合わせ時間O(k+(logn)^d)、空間O(n(logn)^(d-1)))
• バイナリ索引木 - 前処理時間O(n(logn)^d)、問い合わせ時間O((logn)^d)、空間O(n(logn)^d)