14

配列の範囲内で合計を計算する必要があったため、Segment Tree と Fenwick Tree に出会い、これらのツリーの両方が同じ漸近的な実行時間でクエリと更新を行っていることに気付きました。もう少し調査を行ったところ、これら 2 つのデータ構造はすべてを同じ速度で実行しているようです。どちらもメモリ使用量は線形です (セグメント ツリーは 2 倍使用します)。

実行時間/メモリと実装の一定の要因は別として、どちらかを選択する理由はありますか?

私は客観的な答えを探しています。たとえば、一方が他方よりも高速な操作や、一方が他方にない制限があるなどです。

これについて他に 2 つの StackOverflow の質問を見ましたが、回答では、一方が他方よりも優れている場合を説明するのではなく、両方のデータ構造について説明しただけです。

4

4 に答える 4

1

いくつかの追加情報:

  • セグメント ツリーは暗黙的に (ヒープのように) 格納することもできますが、これは2nスペースを占有します。
  • フェンウィック ツリーはオンライン データ構造です。つまり、配列のように最後に要素を追加でき、それは引き続き機能します。デフォルトでは、セグメント ツリーにはこのプロパティがありません。O(log(n))それらを暗黙的に格納している場合は、セグメント ツリーのサイズを 2 倍にすることで (償却された配列と同様に) 分割で追加操作と前置操作の両方を実現できますO(1)。セグメント ツリーがメモリ内でどのように見えるかを調べ、それに応じて新しいスペースを配置する必要があります (余分なスペースをすべて一方の端に配置することはできません)。セグメント ツリーは既にスペース2nを使用しているため、配列を 2 倍にするたびに4nスペースが使用されることに注意してください。
  • フェンウィック ツリーはより高速で、実装が非常に簡単です。漸近境界は同等ですが、最も基本的なクエリと更新のコードは、ほとんど分岐がなく、再帰的ではなく、ほとんど操作を使用しません。これのセグメント ツリー バージョンはほぼ同じ速度で作成できますが、これには余分な労力がかかります。ありがたいことに、これは非常に大きな入力でのみ問題になります。セグメント ツリーを格納すると、暗黙的に優れた空間的局所性が得られ、ポインターを格納する場合と比較して優れたブーストが得られるためです。
  • log(n)Fenwick ツリーは(私の知る限り)で逆クエリを計算できません。つまり、たとえば部分合計を格納していて、どのインデックスiが部分合計に評価されるかを知りたい場合s、それは になりますlog(n)^2。このプロセスはlog(n)、セグメント ツリーでは簡単です。
  • セグメント ツリーで実行できるクエリは他にもさまざまありますが、その多くは Fenwick ツリーでは実行できません。もちろん、この追加の柔軟性には2nストレージ コストがかかります。

編集:このクエリは!で計算できます。log(n)これが私の実装です：

def find(self, s):
    b = 1
    while b < len(bit):
        b <<= 1
    b >>= 1
    index = 0
    cur = 0
    while b > 0:
        if bit[index + b] + cur <= s:
            index += b
            cur += bit[index]
        b >>= 1
    return (index, cur)

これにより、ターゲットの部分合計に最も近いインデックスと合計が返されます (常に <= ターゲットになります)。ただし、これが BIT の負の数で機能するとは思えません。

良いセグメント ツリーの説明: https://cp-algorithms.com/data_structures/segment_tree.html

于 2021-03-21T08:06:08.407 に答える