Fenwick 木

2025年10月22日

Fenwick 木

英語表記: Fenwick Tree (または Binary Indexed Tree: BIT)

概要

Fenwick 木（フェンウィックぎ）は、配列の一点更新と区間和（累積和）の計算を非常に高速に行うために設計された特殊データ構造です。これは、基本的なデータ構造である配列やリストの機能を発展させ、特定の操作の効率を高める目的で開発されました。特に、データ構造の分類における「木構造応用」の文脈で語られることが多く、論理的な木構造の特性を利用して、計算量を劇的に削減することに成功しています。この構造を用いることで、大規模なデータセットに対しても、更新および累積和の取得を対数時間 $O(\log N)$ で実現できるのが最大の魅力です。

詳細解説

Fenwick 木は、データ構造（リスト, スタック, キュー, ツリー）の分類の中でも、特定の課題解決に特化した「特殊データ構造」として位置づけられます。その動作原理は、一見すると配列のように見えますが、内部的には「木構造応用」の考え方に基づいています。

目的と背景：なぜFenwick木が必要なのか

私たちが通常使う配列（リスト）で累積和を管理する場合を考えてみましょう。

配列A（データ本体）を用意し、累積和Sを事前に計算しておく方法:
- 区間和の計算は $O(1)$ で非常に速いです。
- しかし、配列Aの要素が一つ更新されると、累積和Sのそれ以降の要素すべてを再計算する必要があり、更新に $O(N)$ の時間がかかってしまいます。
累積和を計算せず、都度合計する方法:
- 更新は $O(1)$ で済みます。
- しかし、区間和を計算するたびに $O(N)$ の時間がかかってしまいます。

大規模なデータセットにおいて、更新と区間和のクエリが頻繁に発生する場合、上記の方法では処理速度が追いつきません。この課題を解決するために考案されたのが、セグメント木やこのFenwick木のような「特殊データ構造」なのです。Fenwick木は、更新とクエリの両方を $O(\log N)$ という高速な時間で処理することを可能にします。これは本当に素晴らしいことです！

動作原理：最下位ビット（LSB）の魔法

Fenwick木が「木構造応用」と呼ばれるのは、その内部構造が、インデックスのバイナリ表現（2進数）と密接に関連した論理的な木構造を形成しているからです。

Fenwick木は、元の配列の値を直接格納するのではなく、「特定の区間の累積和」を格納する補助配列（ここではBIT配列と呼びます）として機能します。

重要な鍵は「最下位ビット（LSB）」です。

各インデックス $i$ に格納される値は、インデックス $i$ から始まる、ある特定の長さの区間の和です。この特定の長さは、インデックス $i$ を2進数で表したときに、最も右側にある「1」が表す値（LSB）によって決まります。

例えば、インデックスを1から数えると仮定します。

インデックス 6 (110\textsubscript{2}) の LSB は 2 (10\textsubscript{2}) です。
- BIT配列の 6番目の要素は、元の配列の $[5, 6]$ の和を保持します。
インデックス 8 (1000\textsubscript{2}) の LSB は 8 (1000\textsubscript{2}) です。
- BIT配列の 8番目の要素は、元の配列の $[1, 8]$ の和を保持します。

このように、各ノード（インデックス）が責任を持つ区間の長さが2のべき乗（1, 2, 4, 8, …）になっており、これらの区間和を効率的に組み合わせることで、任意の累積和を計算できます。この構造が、実質的に木構造として機能するのです。

更新操作 (Update)

元の配列の $i$ 番目の要素が $\Delta$ だけ変化した場合、その変化を反映させる必要があります。Fenwick木では、この $i$ 番目の要素を含む区間和を保持しているすべてのノード（BIT配列の要素）を更新する必要があります。

更新は、インデックス $i$ からスタートし、LSBを利用して「次に更新すべき親ノード」へジャンプしながら行われます。
具体的には、$i$ に LSB($i$) を足し続けることで、上位の区間和を保持するノードへ移動できます。
このジャンプ操作は、木の高さ（$\log N$）に比例するため、更新は $O(\log N)$ で完了します。

クエリ操作 (Query: 累積和の取得)

$i$ 番目までの累積和を知りたい場合、Fenwick木では、インデックス $i$ からスタートし、LSBを利用して「計算に必要な次の区間和ノード」へジャンプしながら和を合計していきます。

具体的には、$i$ から LSB($i$) を引き続けることで、累積和を構成する必要な区間和ノードへ移動できます。
この操作もまた、木の高さ（$\log N$）に比例するため、クエリも $O(\log N)$ で完了します。

Fenwick木は、セグメント木と比較して実装が非常にシンプルで、使用するメモリ量も少ない（元の配列と同じサイズ $O(N)$）という利点があります。このコンパクトさと高速性こそが、Fenwick木が「特殊データ構造」として高く評価される理由なのです。

具体例・活用シーン

Fenwick木は、その性質上、データの追加や変更が頻繁にあり、かつ区間に関する集計（和、平均など）が求められる場面で真価を発揮します。

1. 予算管理部署の分担（比喩/物語）

Fenwick木を理解するための面白い比喩として、「予算管理の部署の分担」を考えてみましょう。

ある大企業が年間予算を日次で管理しているとします（$N$ 日分の配列）。

通常の管理方法では、誰か一人が担当日以降の予算をすべて手動で再計算する必要があります（$O(N)$）。これでは大変です。

ここで、Fenwick木的な管理方法を導入します。

部署の分担: 担当者は「1日担当」「2日担当」「4日担当」「8日担当」…というように、2のべき乗の日数単位で区間和を管理します。
例: 12日目 (1100\textsubscript{2}) の担当者は、インデックス 12 から LSB (4日) を引いた $[9, 12]$ の4日間の予算を管理する責任を持ちます。
日々の更新: 担当日（例えば12日目）の予算が変わった場合、12日目の担当者だけでなく、その上位の区間（12日目を含む）を管理している担当者（例えば16日担当者など）も更新情報を反映しなければなりません。この伝達は、たった $\log N$ 回の連絡で完了します。
累積和の確認: 「今日（15日目）までにいくら使ったか？」を知りたい場合、15日目の担当者からスタートし、必要な区間を担当している部署（例えば、8日担当、4日担当、2日担当、1日担当の組み合わせ）に順に確認を取っていきます。これも $\log N$ 回の確認で済むのです。

この分担された責任構造こそが、Fenwick木が高速に動作する秘密であり、「木構造応用」の考え方そのものを示しています。

2. 競技プログラミングとデータ分析

頻出度: 競技プログラミングにおいては、Fenwick木は必須の知識の一つです。特に、配列操作と累積和計算が複雑に絡む問題（例：座標圧縮後の区間クエリ）でセグメント木と並んで多用されます。
逆転数の計算: 配列の「逆転数」（順序が逆になっているペアの数）を効率的に数える際にもFenwick木が利用されます。これは、要素を一つずつ処理しながら、それ以前に登場した要素の中で現在の要素より大きいものの個数を累積和の形で取得することで実現されます。
オンラインクエリ: データを読み込みながらリアルタイムで更新や集計を行う「オンライン処理」において、Fenwick木の $O(\log N)$ の高速性は非常に役立ちます。

3. 金融・市場データ処理

株価や取引量の時系列データにおいて、特定の期間（例：直近30日間）の合計値や移動平均を素早く計算し、データの更新（新しい取引の追加）も高速に行う必要がある場合に、Fenwick木は優れたパフォーマンスを発揮します。

資格試験向けチェックポイント

Fenwick木は、高度なアルゴリズムの分野に属するため、ITパスポートや基本情報技術者試験（FE）で直接的に「Fenwick木の実装方法を問う」問題が出題される可能性は極めて低いです。しかし、応用情報技術者試験（AP）やより上位の試験を目指す場合、その概念や計算量、そして他のデータ構造との比較は重要になってきます。

学習のヒント

性能比較の暗記: Fenwick木、セグメント木、単純配列の更新とクエリの計算量（$O(N)$ か $O(\log N)$ か $O(1)$ か）は必ず押さえてください。Fenwick木は両操作とも $O(\log N)$ であることが強みです。
「木構造応用」としての役割: Fenwick木は、リストや配列といった線形構造の弱点（更新またはクエリのどちらかが遅い）を、論理的な木構造を導入することで克服した事例として理解してください。これは特殊データ構造の進化の過程を知る上で非常に重要です。
セグメント木との違い: Fenwick木は主に「和」の計算に特化しており、セグメント木よりもシンプルですが、セグメント木のように「最小値」「最大値」など多様な演算を扱う柔軟性には欠ける場合があります。このトレードオフを覚えておくと、応用レベルの選択肢問題に対応できます。