algorithm - セグメントツリーを使用する場合とBITを使用する場合

Question

シナリオはありません。しかし、私たちが

1. 範囲内で更新します（例では、ある範囲ijのすべての値をクリアします）
2. 範囲内の値を照会します。（RMQの例）
3. 個々の要素を更新します（ポイント1の特定のケース）
4. 範囲内の特定の値を検索します（これもポイント2の特定のケースです）

これらの操作はすべて、BITまたはセグメントツリーのいずれかを使用して実行できますが、3つおよび2つのセグメントツリーの特定のケースを除いて、はるかに効率的です。（実際、BITはRMQのようなクエリにはまったく役立ちません）

BITの最も明らかな利点は、コーディングがはるかに簡単なことです。

Answer 1

(数週間前からセグメント ツリーと BIT の問題に時間を費やした後の私の考えは、まったく新しいものです)

BIT はコーディングが簡単ですが、簡単に視覚化してセグメント ツリーに関連付けることができる状況があります。BIT が提供するもう 1 つの利点は、使用するスペースが少ない (O(n) スペース) ことです。

BITに比べて分節木の方が分かりやすいので、状況に合わせて応用しやすいと思います。セグメント ツリーでは、遅延伝播もより単純で理解しやすくなります。したがって、セグメント ツリーを使用すると、範囲を効率的に更新できます。