22

フェンウィック ツリーは、主なクエリに答える効率的な方法を提供するデータ構造です。

  • 配列の特定のインデックスに要素を追加するupdate(index, value)
  • 1 から N までの要素の和を求めるfind(n)

両方の操作は時間内に完了し、ロジックと実装O(log(n))を理解しています。N から M の合計を求めるなど、他の多くの演算を実装するのは難しくありません。

フェンウィック ツリーを RMQ に適応させる方法を理解したかったのです。最初の 2 つの操作でフェンウィック ツリーを変更することは明らかです。しかし、N から M までの範囲で最小値を見つける方法がわかりません。

解決策を探した後、大多数の人はこれは不可能だと考えており、実際にはできると主張する少数派もいます (アプローチ1 、アプローチ2 )。

最初のアプローチ (ロシア語で書かれており、Google 翻訳には説明がなく、関数は 2 つしかないことに基づいています) は、考えられるすべてのテスト ケースでテストが正しく機能しなかったため、3 つの配列 (初期、左、右) に依存しています。

2 番目のアプローチでは、必要なアレイは 1 つだけであり、要求に基づいて実行されO(log^2(n))ますが、それが機能する理由と方法についての説明もほとんどありません。私はそれをテストしようとはしていません。

update(index, value)物議を醸す主張に照らして、フェンウィック木を拡張してとを答えられるかどうかを調べたかったのfindMin(from, to)です。

可能であれば、その仕組みをお聞かせいただければ幸いです。

4

2 に答える 2

25

はい、Fenwick Trees (Binary Indexed Trees) を次のように適応させることができます。

  • O(log n) の特定のインデックスで値を更新する
  • O(log n) の範囲の最小値を照会 (償却)

2 つの Fenwick ツリーと、ノードの実際の値を保持する追加の配列が必要です。

次の配列があるとします。

index 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
value 1  0  2  1  1  3  0  4  2  5  2  2  3  1  0

魔法の杖を振ると、次の木が現れます。

問題の例としてのフェンウィックの木

両方のツリーで、各ノードがそのサブツリー内のすべてのノードの最小値を表すことに注意してください。たとえば、BIT2 ではノード 12 の値は 0 で、これはノード 12、13、14、15 の最小値です。

クエリ

いくつかのサブツリー値の最小値と 1 つの追加の実ノード値を計算することにより、任意の範囲の最小値を効率的にクエリできます。たとえば、範囲 [2,7] の最小値は、BIT2_Node2 (ノード 2、3 を表す) と BIT1_Node7 (ノード 7 を表す)、BIT1_Node6 (ノード 5、6 を表す)、および REAL_4 の最小値を取得することによって決定できます。 [2,7] のすべてのノードをカバーします。しかし、どのサブツリーを見たいかをどうやって知るのでしょうか?

Query(int a, int b) {
  int val = infinity // always holds the known min value for our range

  // Start traversing the first tree, BIT1, from the beginning of range, a
  int i = a
  while (parentOf(i, BIT1) <= b) {
    val = min(val, BIT2[i]) // Note: traversing BIT1, yet looking up values in BIT2
    i = parentOf(i, BIT1)
  }

  // Start traversing the second tree, BIT2, from the end of range, b
  i = b
  while (parentOf(i, BIT2) >= a) {
    val = min(val, BIT1[i]) // Note: traversing BIT2, yet looking up values in BIT1
    i = parentOf(i, BIT2)
  }

  val = min(val, REAL[i]) // Explained below
  return val
}

両方のトラバーサルが同じノードで終了することは、数学的に証明できます。そのノードは範囲の一部ですが、これまで見てきたサブツリーの一部ではありません。範囲の (一意の) 最小値がその特別なノードにある場合を想像してください。それを調べなければ、アルゴリズムは間違った結果をもたらすでしょう。これが、実際の値の配列を 1 回検索する必要がある理由です。

アルゴリズムの理解を助けるために、ペンと紙を使ってシミュレートし、上記のサンプル ツリーのデータを調べることをお勧めします。たとえば、範囲 [4,14] のクエリは、BIT2_4 (rep. 4,5,6,7)、BIT1_14 (rep. 13,14)、BIT1_12 (rep. 9,10,11、 12) および REAL_8 であり、すべての可能な値をカバーします [4,14]。

アップデート

ノードはそれ自体とその子の最小値を表すため、ノードを変更すると親には影響しますが、子には影響しません。したがって、ツリーを更新するには、変更しているノードから開始し、架空のルート ノード (ツリーに応じて 0 または N+1) まで上に移動します。

あるツリーのノードを更新するとします。

  • 新しい値 < 古い値の場合、常に値を上書きして上に移動します
  • 新しい値 == 古い値の場合、上にカスケードする変更がなくなるため、停止できます。

  • 新しい値 > 古い値の場合、事態は興味深いものになります。

    • そのサブツリー内のどこかに古い値がまだ存在する場合は、完了です。
    • そうでない場合は、実[ノード]と各ツリー[ノードの子]の間の新しい最小値を見つけ、ツリー[ノード]を変更して上に移動する必要があります

ツリー内の値 v を持つノードを更新するための疑似コード:

while (node <= n+1) {
  if (v > tree[node]) {
    if (oldValue == tree[node]) {
      v = min(v, real[node])
      for-each child {
        v = min(v, tree[child])
      }
    } else break
  }
  if (v == tree[node]) break
  tree[node] = v
  node = parentOf(node, tree)
}

oldValue は置き換えた元の値であることに注意してください。一方、v は、ツリーを上に移動するときに複数回再割り当てされる可能性があります。

バイナリ インデックス作成

私の実験では、Range Minimum クエリはセグメント ツリーの実装よりも約 2 倍高速で、更新はわずかに高速でした。これの主な理由は、ノード間の移動に非常に効率的なビット演算を使用しているためです。それらはここで非常によく説明されています。セグメント ツリーは非常に簡単にコーディングできるため、パフォーマンス上の利点が本当に価値があるかどうかを考えてみてください。私の Fenwick RMQ の update メソッドは 40 行あり、デバッグに時間がかかりました。誰かが私のコードを必要とする場合は、github に置くことができます。また、ブルート ジェネレーターとテスト ジェネレーターを作成して、すべてが機能することを確認しました。

フィンランドのアルゴリズム コミュニティから、このテーマの理解と実装を手伝ってもらいました。画像のソースはhttp://ioinformatics.org/oi/pdf/v9_2015_39_44.pdfですが、フェンウィックの 1994 年の論文の功績によるものです。

于 2016-01-05T00:20:11.707 に答える
1

加算は可逆であるため、フェンウィック ツリー構造は加算に対して機能します。2つ以上の入力の最小値であるはずのセルがあるとすぐに、情報が失われる可能性があるため、最小値では機能しません。

ストレージ要件を 2 倍にしたい場合は、バイナリ ヒープのように暗黙的に構築されるセグメント ツリーを使用して RMQ をサポートできます。n 個の値を持つ RMQ の場合、n 個の値を配列の位置 [n, 2n) に格納します。位置 [1, n) は、式 A(k) = min(A(2k), A(2k+1)) の集計です。場所 2n は無限の歩哨です。更新ルーチンは次のようになります。

def update(n, a, i, x):  # value[i] = x
    i += n
    a[i] = x
    # update the aggregates
    while i > 1:
        i //= 2
        a[i] = min(a[2*i], a[2*i+1])

ここでの乗算と除算は、効率のためにシフトに置き換えることができます。

RMQ 疑似コードはよりデリケートです。これは、テストも最適化もされていない別のルーチンです。

def rmq(n, a, i, j):  # min(value[i:j])
    i += n
    j += n
    x = inf
    while i < j:
        if i%2 == 0:
            i //= 2
        else:
            x = min(x, a[i])
            i = i//2 + 1
        if j%2 == 0:
            j //= 2
        else:
            x = min(x, a[j-1])
            j //= 2
    return x
于 2015-06-29T02:41:26.567 に答える