【フェニックぎ】
フェニック木（BIT） とは？
公開:
💡 合計を、2進数でたどれる小分けの箱に
配列の部分和を管理し、1点への加算と先頭からの合計を効率よく扱うデータ構造。添字の2進表現を利用して、必要な区間だけをたどる。
📌 このページのポイント
- 代表的な用途は、1点への加算と先頭からの和の取得
- n要素なら両操作をO(log n)時間、保存領域をO(n)で扱える
- 区間和は二つの累積和の差で求めるが、最小値などにそのまま置き換えられるわけではない
ひよこ 普通の累積和とは何が違うの？
ペンギン先生 累積和を全部並べておくと区間の和はすぐ求められるけれど、途中の値を変えると後ろの和も更新しなければならないよね。フェニック木は、合計をいくつかの区間に分けて持ち、更新と問い合わせの両方を軽くするんだ。
ひよこ どんな区間を持つの？
ペンギン先生 このページでは添字を1から数えるよ。tree[i]はiで終わる区間の和で、その長さはiの2進表現の一番右の1が表す値。たとえば6は110なので長さ2、tree[6]は5〜6番目の和だよ。4は100なので、tree[4]は1〜4番目を持つんだ。
ひよこ 6番目までの和はどう取るの？
ペンギン先生 添字を6→4→0とたどり、tree[6]とtree[4]を足すよ。配列が[3,1,4,1,5,9,2,6]なら、5〜6番目の和14と1〜4番目の和9で23になる。区間が重ならず、先頭から6番目までをちょうど覆うんだ。
ひよこ 値を変えるときも同じ道をたどるの？
ペンギン先生 更新では、その値を含む区間へ加算する別の道をたどるよ。8要素で3番目に2を足すなら、tree[3]、tree[4]、tree[8]へ2ずつ加える。和の取得も更新も、添字をビット操作で進めることでO(log n)回の処理に抑えられるんだ。
もっと詳しく知りたい人へ
区間の最小値も、累積値の差で求められますか？
いいえ。和ならsum(r)−sum(l−1)で区間[l,r]を求められますが、最小値には同じ引き算がありません。演算や更新方法を制限した拡張はありますが、基本形の加算・区間和の性質を任意の演算に一般化しません。
まとめ：ざっくりこれだけ覚えればOK！
「フェニック木（BIT）」って出てきたら「添字のビットを使って、更新と累積和を効率よく扱う構造」と思えればだいたいOK！