フェンウィックの木

フェンウィックツリー
バイナリインデックスツリー
フェンウィックツリー; バイナリインデックスツリー
タイプ	二項木
発明された	1989
発明者	ボリス・リャブコ
手術
ビッグO記法による時間計算量
手術	平均
検索	O(log n )
入れる	O(log n )
空間複雑性
空間	の上）

データ構造

フェンウィック木または二分索引木 （BIT）は、値の配列を格納し、値のプレフィックス和を効率的に計算し、値を更新できるデータ構造です。また、合計が指定された値以下となる最長プレフィックスを見つけるための効率的な順位検索演算もサポートしています。主な用途は、頻繁に更新される統計頻度表の累積分布関数に対する演算です。

この構造は1989年にボリス・リャブコによって提案され^[1] 、1992年にさらなる改良が発表されました^[2]。その後、1994年の論文でこの構造を説明したピーター・フェンウィックにちなんで、フェンウィックツリーという名前で知られるようになりました^{[3] 。}

単純な値の配列は更新が簡単（一定時間）ですが、プレフィックスの合計を計算したり、プレフィックスの長さを検索したりするには時間がかかります。 $O(n)$

プレフィックスの合計の配列は、一定時間内にプレフィックスの合計を返し、時間内にプレフィックスの長さを検索できますが、値の 1 つを更新するのには時間がかかります。 $O(\log n)$ $O(n)$

フェンウィック木は、これら3つの操作すべてを時間内に実行することを可能にします。これは、値をノードを持つ木として表現することで実現されます。木内の各ノードは、親のインデックス（排他的）からノードのインデックス（包含的）までの値の合計を格納します。木自体は暗黙的であり、値の配列として格納できます。この場合、暗黙的なルートノードは配列から省略されます。この木構造により、値の取得、値の更新、プレフィックスの合計、範囲の合計といった操作を、ノードアクセスのみで実行できます。 $O(\log n)$ $n+1$ $n$ $O(\log n)$

モチベーション

値の配列が与えられた場合、連想二項演算（最も一般的なのは整数の加算）に従って各インデックスまでの値の累計を計算したい場合があります。フェンウィックツリーは、任意のインデックスにおける累計、つまりプレフィックス合計を照会する手段を提供します。また、基になる値の配列を変更し、それ以降のすべてのクエリにその変更を反映させることができます。

フェンウィック木は、特に適応算術符号化を実装するために設計されています。適応算術符号化では、生成された各シンボルのカウントを保持し、それを特定のシンボルよりも小さいシンボルの累積確率に変換する必要があります。フェンウィック木がサポートする演算の開発は、主にこのケースでの使用を動機としていました。^[要出典]

説明

フェンウィックツリーは、ノードに連続番号が付けられ、親子関係がノードインデックスの算術演算によって決定される暗黙的なツリーです。

このインデックス演算において重要な機能は、最下位ビットです。これはインデックスを割り切れる2の最大のべき乗です。これは2のべき乗 (1, 2, 4, 8, ...) であり、指数 (0, 1, 2, 3, ...) ではありません。これは 2の補数演算で次のように効率的に計算できます(ここで & はビットごとのAND を表します)。 $i$ $\operatorname {lsb} (i)=i\mathbin {\&} -i$

フェンウィックツリーは、1から始まる配列の値を用いると最も簡単に理解できます。半開区間構文を用いて、範囲を（含まない）から（含む）とします。対応するフェンウィック配列には、範囲の合計が格納されます。つまり、で終わり、を含む値の合計です。 $A[n]$ $n$ $A(i,j]=\{A[k]\}_{k=i+1}^{j},$ $i$ $j$ $F[n]$ $\textstyle F[i]=\sum A(i-\operatorname {lsb} (i),i]$ $\operatorname {lsb} (i)$ $A[i]$

いくつかの説明では架空のノード 0 が使用されていますが、実際にはアクセスされず、明示的に保存する必要もありません。ただし、値が実際に必要になることはありません。値 0 の空の範囲の合計が含まれていると考えられます。 $\operatorname {lsb} (0)=\infty ,$ $F[0]$ $A(0,0]=\{\}$

「フェンウィック木」は、実際には同じ配列上の3つの暗黙的な木です。インデックスをプレフィックスの合計に変換するために使用される問い合わせ木、要素を更新するために使用される更新木、そしてプレフィックスの合計をインデックスに変換する（ランク付けクエリ）ための検索木です。 ^[4] 最初の2つは通常上向きに探索され、3つ目は下向きに探索されます。

尋問ツリー

問い合わせツリーは、ノードの親がとなるように定義されます。例えば、 6 = 110 ₂の親は4 = 100 ₂です。暗黙のノード 0 がルートです。 $i$ $i-\operatorname {lsb} (i)=i\mathbin {\&} (i-1)$

木の各レベルには、2の異なる累乗の和に対応するインデックスを持つノードが含まれます（ただし、0は空の和を表します）。例えば、レベルにはノードが含まれ、レベルにはノードが含まれます。 $k$ $k$ $k=0$ $k=1$ $1=2^{0},2=2^{1},4=2^{2},...$ $k=2$ $3=2^{1}+2^{0},5=2^{2}+2^{0},6=2^{2}+2^{1},...$

ノードには子 ( )、および子孫の合計数があります。 (これらの数には、より大きいノードも含まれますが、これらは省略され、アクセスされることはありません。) $i$ $\log _{2}(\operatorname {lsb} (i))$ $i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2$ $\operatorname {lsb} (i)$ $n$

下の図は、ルートを含む 16 ノードのフェンウィックツリーの照会ツリーの構造を示しており、15 要素の配列 A に対応します。

プレフィックス和を求めるには、、その親、その親の親、といった具合に、ルートまで（ルートは含まない）の値を合計します。範囲和を求めるには、とのプレフィックス和を減算します。 $A[1]+\cdots +A[i]$ $i$ $A[i]+\cdots +A[j]$ $i-1$ $j$

これは、最初の共通祖先で停止することで最適化できます。極端な例として、単一のエントリを求める場合を考えてみましょう。この場合、との共通祖先はなので、から始めて、である限りを減算してを更新します。 $A[j]$ $j$ $i=j-1$ $j-\operatorname {lsb} (j)$ $F[j]$ $i\neq j-\operatorname {lsb} (j)$ $F[i]$ i := i - lsb(i)

更新ツリー

更新木は問い合わせ木の鏡像です。ノードの親は（|はビット論理和を表します）です。例えば、6 = 110 ₂の親は8 = 1000 ₂です。 $i$ $i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1$

この概念ツリーは無限ですが、インデックスがまでの部分のみが保存または使用されます。より大きいインデックスを持つ架空のノードを除外すると、のバイナリ表現の各ビットセットに対応する、互いに素なツリーのフォレストが作成されます。 $n$ $n$ $n$

ここで、ノードの祖先とは、自身の範囲の合計を含むすべてのノードを指します。例えば、はの合計を保持し、はの合計を保持します、などです。 $F[6]$ $A(4,6]$ $F[8]$ $A(0,8]$

値の 1 つを変更するには、に変更を追加し、次にの親、さらにその祖父母というように、インデックスがを超えるまで変更を追加します。 $A[i]$ $F[i]$ $i$ $n$

検索ツリー

他の2つの木とは異なり、探索木は二分木であり、クヌースが「横向きヒープ」と呼ぶ順序で配置されています。^[5] 各ノードには、そのインデックスの二分表現の末尾のゼロの数に等しい高さが割り当てられ、親と子は隣接する高さの数値的に最も近いインデックスになります。奇数インデックス ( ) のノードは葉です。偶数インデックスのノードには、次に低いインデックスの最も近い2つのノードが子としてあります。探索木におけるノードの親はです。 $\operatorname {lsb} (i)=1$ $i\pm \operatorname {lsb} (i)/2$ $i$ $(i-\operatorname {lsb} (i))\mathbin {|} (2\cdot \operatorname {lsb} (i))$

たとえば、 6 = 110 ₂の子は5 = 101 ₂と 7 = 111 ₂であり、親は 4 = 100 ₂です。

このツリーは潜在的に無限ですが、そのルートを、インデックスが 2 の最大の累乗以下である最上位の既存ノードとして定義することができます。 $n$

ノードが、インデックスがより大きい架空の親を持ちながら、既存の祖父母を持つ場合があります。上記の例を5ノードのツリーに適用すると、ノード5は架空の親6を持ちますが、既存の祖父母4を持ちます。 $n$

探索木は、前述の2つの木を組み合わせたものと考えることができます。ノードの左サブツリーには更新木内のすべての子孫が含まれ、右サブツリーには問い合わせ木内のすべての子孫が含まれます。探索木におけるノードの親は、（ノードが右子か左子かに応じて）問い合わせ親または更新親のいずれかであり、もう一方の親は、探索木を複数回上方に進むことで見つかる場合があります。

しかし、探索木の上方向のトラバーサルは一般的ではありません。その主な用途は、順位付けクエリを実行することです。つまり、プレフィックスの合計が与えられた場合、それがどのインデックスに現れるかを調べます。これは、探索木を下方向へトラバーサルすることで行われます。トラバーサル中は、3つの変数が維持されます。現在のノードのインデックス、現在のノードをルートとするサブツリー内で検索する順位、そして、検索する順位がサブツリー内で見つかる順位よりも大きい場合に返される「フォールバックインデックス」です。

初期状態では、現在のノードはルート、検索対象となるランクは元のクエリ、フォールバックインデックスは、ランクがツリー内に存在しないことを示す特別な「オーバーフロー」値です。（アプリケーションによっては、またはがこの目的で使用される場合があります。） $0$ $n+1$

各ステップでは、現在のノードが架空のノード（インデックスがより大きい）であるか、または検索する位置が現在のノードの末尾の左側か右側かを判断する必要があります。検索するランクが現在のノードのFenwick配列の値より小さい場合は、その左側のサブツリーを検索する必要があります。大きい場合は、右側のサブツリーを検索します。等しい場合は、2つのノードの間にある合計の検索をどのように処理するかによって、選択される方向が異なります。 $n$ $F[i]$

これら 3 つの可能性は、現在のノードがリーフであるかどうかに基づいてさらに分類されます。

現在のノードがリーフであり、
- ターゲットが（空の）左サブツリー内にある場合は、現在のインデックスを返します。
- それが架空のものであるか、ターゲットが右側のサブツリー内にある場合は、フォールバックインデックスを返します。
現在のノードがリーフ ではなく、次の場合:
- これは架空のものであるため、変更されていないフォールバックインデックスを使用して、左のサブツリーで同じランクを検索します。
- ターゲットが左のサブツリー内にある場合、現在のインデックスをフォールバックインデックスとして、左のサブツリー内で同じランクを検索します。
- ターゲットが右のサブツリー内にある場合、フォールバックインデックスを変更せずに、右のサブツリー内のターゲットランクから現在のノードの値を引いた値を検索します。

擬似コード

フェンウィックツリーの 2 つの主要な操作 (クエリと更新) の簡単な疑似コード実装は次のとおりです。

関数query(tree, index)は
    合計 := 0
    インデックス > 0の場合は
        合計 += ツリー[インデックス]
        インデックス -= lsb(インデックス)
    合計を返す

関数update(tree, index, value)は、
     index < size(tree)の場合に実行されます。
        ツリー[インデックス] += 値
        インデックス += lsb(インデックス)

この関数は、与えられたの最下位ビット、つまりの約数でもある2の最大のべき乗を計算します。例えば、は2進数で表すととなります。この関数は、 2の補数の否定を仮定し、ビットごとのAND演算によってコードに簡単に実装できます。^[3] ${\text{lsb}}(n)$ $n$ $n$ ${\text{lsb}}(20)=4$ ${\text{lsb}}(10{\textbf {1}}00_{2})=100_{2}=4$ lsb(n) = n & (-n)

工事

フェンウィック木を構築するための単純なアルゴリズムの一つは、木をnull値で初期化し、各インデックスを個別に更新するというものである。この解法は時間的にも有効だが、次のような構築方法も可能である。^[6] $O(n\log {n})$ $O(n)$

関数construct(values)は
    ツリー := 値
    1からsize(tree)までのインデックスに対して、
        親インデックス := インデックス + lsb(インデックス)
        親インデックス≤サイズ(ツリー)の場合
            ツリー[親インデックス] += ツリー[インデックス]
    リターンツリー

参照

参考文献

^ Boris Ryabko (1989). 「高速オンラインコード」(PDF) .ソビエト数学. Dokl . 39 (3): 533– 537. 2019年7月17日時点のオリジナルよりアーカイブ(PDF) . 2019年7月17日閲覧。
^ Boris Ryabko (1992). 「高速オンライン適応型コード」(PDF) . IEEE Transactions on Information Theory . 28 (1): 1400– 1404. 2019年7月14日時点のオリジナルよりアーカイブ(PDF) . 2019年7月14日閲覧。
^ ab Peter M. Fenwick (1994). 「累積頻度表のための新しいデータ構造」.ソフトウェア：実践と経験. 24 (3): 327– 336. CiteSeerX 10.1.1.14.8917 . doi :10.1002/spe.4380240306. S2CID 7519761.
^ Marchini, Stefano; Vigna, Sebastiano (2019年10月14日). 「Compact Fenwick trees for dynamic ranking and selection」. arXiv : 1904.12370 [cs.DS]. 実用的な実装の詳細に関する広範な議論。
^ Knuth, Donald (2011).組み合わせアルゴリズム第1部. 『コンピュータプログラミングの芸術』第4A巻. アッパーサドルリバー, ニュージャージー州: Addison-Wesley Professional. pp. 164– 165.
^ ハリム、スティーブン;ハリム、フェリックス。エフェンディ、スヘンドリー（2018年12月3日）。競技プログラミング４． Vol. 1. ルルプレス株式会社。ISBN 978-1-716-74552-2。

外部リンク

TopCoderのFenwick Treesのチュートリアル
AlgorithmistのFenwick Treesに関する記事
Polymath wikiのFenwick Treesに関するエントリ
スタック交換

[1] Boris Ryabko (1989). 「高速オンラインコード」(PDF) .ソビエト数学. Dokl . 39 (3): 533– 537. 2019年7月17日時点のオリジナルよりアーカイブ(PDF) . 2019年7月17日閲覧。

[2] Boris Ryabko (1992). 「高速オンライン適応型コード」(PDF) . IEEE Transactions on Information Theory . 28 (1): 1400– 1404. 2019年7月14日時点のオリジナルよりアーカイブ(PDF) . 2019年7月14日閲覧。

[:0-3] Peter M. Fenwick (1994). 「累積頻度表のための新しいデータ構造」.ソフトウェア：実践と経験. 24 (3): 327– 336. CiteSeerX 10.1.1.14.8917 . doi :10.1002/spe.4380240306. S2CID 7519761.

[4] Marchini, Stefano; Vigna, Sebastiano (2019年10月14日). 「Compact Fenwick trees for dynamic ranking and selection」. arXiv : 1904.12370 [cs.DS]. 実用的な実装の詳細に関する広範な議論。

[5] Knuth, Donald (2011).組み合わせアルゴリズム第1部. 『コンピュータプログラミングの芸術』第4A巻. アッパーサドルリバー, ニュージャージー州: Addison-Wesley Professional. pp. 164– 165.

[cp4-6] ハリム、スティーブン;ハリム、フェリックス。エフェンディ、スヘンドリー（2018年12月3日）。競技プログラミング４． Vol. 1. ルルプレス株式会社。ISBN 978-1-716-74552-2。