フェンウィックの木

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

フェンウィックツリーまたはバイナリ インデックス ツリー (BIT)は、値の配列を格納し、値のプレフィックスの合計を効率的に計算して値を更新できるデータ構造です。また、合計が指定された値を超えない最長プレフィックスを見つけるための効率的なランク検索操作もサポートしています。主な用途は、頻繁に更新される 統計頻度表の累積分布関数を操作することです。

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

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

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

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

値の配列が与えられた場合、連想バイナリ演算(最も一般的なのは整数の加算)に従って各インデックスまでの値の累積合計を計算することが望ましい場合があります。フェンウィック ツリーは、基になる値の配列を変更し、それ以降のすべてのクエリにそれらの変更を反映させながら、任意のインデックスで累積合計またはプレフィックス合計をクエリする方法を提供します。

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

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

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

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

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

「フェンウィックツリー」は、実際には同じ配列上の3つの暗黙的なツリーです。インデックスをプレフィックスの合計に変換するために使用される照会ツリー、要素を更新するために使用される更新ツリー、およびプレフィックスの合計をインデックスに変換する（ランククエリ）ための検索ツリーです。 ^[4] 最初の2つは通常上向きに走査され、3番目は通常下向きに走査されます。

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

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

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

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

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

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

更新ツリーは照会ツリーのミラー イメージです。ノードの親は(| はビット OR を表します)です。たとえば、6 = 110 ₂の親は8 = 1000 ₂です。 ${\displaystyle i}$${\displaystyle i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1}$

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

ここで、ノードの祖先とは、範囲の合計に自身の合計が含まれるすべてのノードです。たとえば、 はの合計を保持し、は の合計を保持します。${\displaystyle F[6]}$${\displaystyle A(4,6]}$${\displaystyle F[8]}$${\displaystyle A(0,8]}$

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

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

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

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

ノードに、インデックスが より大きい架空の親があり、さらに既存の祖父母が存在する可能性があります。上記の例を 5 ノードのツリーに適用すると、ノード 5 には架空の親 6 がありますが、既存の祖父母は 4 になります。 ${\displaystyle n}$

検索ツリーは、前の 2 つのツリーの組み合わせと考えることができます。ノードの左のサブツリーには更新ツリー内のすべての子孫が含まれ、右のサブツリーには照会ツリー内のすべての子孫が含まれます。検索ツリー内のノードの親は、照会親または更新親のいずれか (それぞれノードが右の子か左の子かによって異なります) であり、他の種類の親は、検索ツリーを複数回上向きに進めることで見つかる場合があります。

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

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

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

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

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

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

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

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

この関数は、指定された の最下位1 ビットまたは最後のセット ビット、または同等に、の約数でもある2 の最大の累乗を計算します。たとえば、 は、そのバイナリ表現で次のように示されます。この関数は、 2 の補数の否定を前提として、ビット単位の AND演算 を介してコードで簡単に実装できます。 ^[3]${\displaystyle {\text{lsb}}(n)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle {\text{lsb}}(20)=4}$${\displaystyle {\text{lsb}}(10{\textbf {1}}00_{2})=100_{2}=4}$lsb(n) = n & (-n)

フェンウィック木を構築するための単純なアルゴリズムの1つは、木をnull値で初期化し、各インデックスを個別に更新することです。この解決策は時間内に機能しますが、構築は可能です：^[6]${\displaystyle O(n\log {n})}$${\displaystyle O(n)}$

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

• 順序統計ツリー
• プレフィックス合計
• セグメントツリー

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