フェニック木

フェニック木 (Binary Indexed Tree) とは

フェニック木（Binary Indexed Tree, BIT）は、数列における部分和の計算と要素の更新を高速に行うことができるデータ構造です。1994年にピーター・フェニックによって、算術符号化アルゴリズムの効率化のために提案されました。

通常の数列でデータを管理する場合、要素そのものを格納する方法と区間和を格納する方法が考えられます。要素をそのまま格納する場合、区間和の計算には区間の長さに比例した時間がかかり、区間和を格納する場合は要素の更新に数列の長さに比例した時間がかかります。しかし、フェニック木を用いると、要素の更新と区間和の計算の両方を O(log n) の時間計算量で実行できます。

フェニック木は、木構造に基づいたデータ構造でありながら、実際には1次元配列を用いて実装されることが一般的です。各ノードの値は、そのノードが担当する部分木の要素の和を表しており、この性質を利用して効率的な計算を実現しています。

開発の背景

算術符号のようなアルゴリズムでは、数列の各インデックスまでの部分和を頻繁に計算する必要があります。また、データの更新も頻繁に行われるため、効率的なデータ構造が求められます。フェニック木は、このようなニーズに応えるために開発されました。特に、算術符号化では文字の出現頻度や累積確率の計算にフェニック木が活用されています。

フェニック木の利点

フェニック木を使用することで、以下のことが可能になります。

部分和の高速計算: 任意のインデックスまでの部分和を O(log n) の時間で計算できます。
区間和の高速計算: 任意の区間の和も O(log n) の時間で計算できます。
要素の高速更新: 要素の値を更新する際も、関連する部分木の値を O(log n) の時間で更新できます。
多次元配列への拡張: フェニック木は多次元配列にも拡張可能であり、それぞれの操作を O(4^d log_d n) の時間で行うことができます。ここで、d は次元数、n は各次元の要素数です。

フェニック木の仕組み

フェニック木は、内部的には1次元配列で表現されます。各要素は、対応する部分木の要素の和を保持しています。この構造により、効率的な部分和計算と要素更新が実現されます。

ノードの親子関係

あるノードのインデックスが与えられたとき、その親ノードや子ノードのインデックスは、ビット演算を用いて計算できます。例えば、親ノードのインデックスは、現在のインデックスの最下位の '1' のビットを '0' にすることで得られます。

部分和の計算方法

部分和を計算する際には、対象のインデックスを2進数で表現し、'1' のビットに対応する要素を足し合わせます。これにより、O(log n) の時間で部分和を計算できます。

例えば、最初の11要素の和を計算する場合、11を2進数で表すと1011となります。この場合、インデックス1000, 1010, 1011の要素を足し合わせることで、1から11までの和を計算できます。

要素の更新方法

要素の更新時には、更新対象のインデックスから、親ノードを順に辿りながら、関連する部分木の値を更新します。この操作も O(log n) の時間で完了します。

例えば、11番目の要素を更新する場合、インデックス1011, 1100, 10000の要素を更新する必要があります。

前処理

フェニック木を作成する際の前処理は O(n) の時間で完了します。

その他の応用

フェニック木は、部分和の計算以外にも、以下のような応用が可能です。

値の検索：すべての値が正の場合、値のインデックスを効率的に検索できます。
値の指定：すべての値が負でない場合、すべてのインデックスの値を効率的に指定できます。
定数倍：すべての係数を O(n) の時間で定数倍することができます。

実装例

以下にC言語による簡単な実装例を示します。この実装では、他の手法との比較も含まれています。実際のプログラムでは、数列のサイズやデータの特性に合わせて最適な実装を選ぶと良いでしょう。

c
// C言語によるフェニック木の実装例（簡略化）
int fenwick_tree[MAX_SIZE];

void update(int index, int value) {
while (index < MAX_SIZE) {
fenwick_tree[index] += value;
index += (index & -index);
}
}

int query(int index) {
int sum = 0;
while (index > 0) {
sum += fenwick_tree[index];
index -= (index & -index);
}
return sum;
}

まとめ

フェニック木は、部分和計算と要素更新を効率的に行うための強力なデータ構造です。算術符号化をはじめ、さまざまなアルゴリズムやアプリケーションで活用されています。そのシンプルさと高いパフォーマンスにより、実用的なデータ構造として広く利用されています。

参照

級数

参考文献

（参考文献の情報を追加してください）

外部リンク

A tutorial on Fenwick Trees on TopCoder
An article on Fenwick Trees on Algorithmist
An entry on Fenwick Trees on Polymath wiki

もう一度検索