C++で学ぶバイナリインデックスツリー（フェンウィック木）の仕組みと実装

競技プログラミングやアルゴリズム設計の現場で頻繁に活用されるデータ構造に、バイナリインデックスツリー（Binary Indexed Tree、通称フェンウィック木）があります。本記事では、その基本的な考え方から、実際のC言語・C++による実装例までをわかりやすく解説します。

なぜフェンウィック木が必要なのか？

単純な数値の配列と比較すると、フェンウィック木は「要素の更新」と「接頭辞和（プレフィックスサム）の計算」という2つの操作のバランスを大きく改善できる点が魅力です。

長さ m の通常の配列を考えた場合、選択肢は次の2つしかありません。

• 配列そのものを保持する場合： 要素の更新は定数時間 O(1) で行えますが、先頭からある位置までの和を求めるには線形時間 O(m) かかります。
• 接頭辞和をあらかじめ保持する場合： 和の計算は定数時間 O(1) で済みますが、1つの要素を更新するたびに配列全体を書き直す必要があり、更新には線形時間 O(m) かかります。

一方、フェンウィック木を使えば、どちらの操作も O(log m) の時間で実行できます。これは、数値を木構造として表現し、各ノードの値を「その部分木に含まれる数値の総和」として管理することで実現されます。木構造のおかげで、操作は O(log m) 回のノードアクセスだけで完了します。

フェンウィック木の構造：1始まりのインデックスで理解する

フェンウィック木は、1始まり（one-based）の配列として考えると最も理解しやすい構造です。

• インデックス j が2の累乗である要素は、最初の j 個の要素の総和を保持します。
• それ以外の要素は、「直前の2の累乗の位置以降」の要素の総和を保持します。

つまり、各要素は「木における自分の親以降の値の総和」を表しており、この親はインデックスの最下位ビット（LSB）を0にクリアすることで見つけることができます。

接頭辞和の計算方法

任意の位置（インデックス）までの和を求めるには、そのインデックスを2進数展開し、2進表現において「1」となるビットに対応する要素を順に加算していきます。

具体例： 最初の11個の値の総和を求めたいとします。11は2進数で 1011 です。1のビットが3つあるため、3つの要素を加算すればよいことになります。

• 1000 → 値 1〜8 の総和
• 1010 → 値 9〜10 の総和
• 1011 → 値 11 の総和

これら3つを足し合わせることで、1〜11の総和が効率的に得られます。

C言語によるシンプルな実装例

以下は、フェンウィック木をC言語で実装したシンプルなコードです。

#define LSB(i) ((i) & -(i)) // 最下位ビット以外をすべて0にするマクロ
int A1[SIZE];

// インデックス1からiまでの総和を返す
int sum(int i) {
    int sum = 0;
    while (i > 0)
        sum += A1[i], i -= LSB(i);
    return sum;
}

// インデックスiの要素にkを加算する
void add(int i, int k) {
    while (i < SIZE)
        A1[i] += k, i += LSB(i);
}

コードのポイント

• LSB(i) マクロは i & -i というビット演算により、i の最下位ビットだけを取り出します。
• sum 関数は、インデックスからLSBを繰り返し引くことで、担当範囲の要素を順に加算します。
• add 関数は逆に、インデックスへLSBを繰り返し加算しながら、影響を受けるすべてのノードを更新します。

まとめ

フェンウィック木（バイナリインデックスツリー）は、要素の更新と区間和の計算をどちらも O(log m) で処理できる非常に強力なデータ構造です。実装も数十行程度とコンパクトでありながら、累積和の高速な再計算が必要となる場面——例えば競技プログラミングのクエリ処理や、統計情報の動的な集計など——で大きな効果を発揮します。ビット演算の仕組みさえ押さえれば応用範囲は広いため、ぜひマスターしておきたいテクニックの一つです。