Fenwick 木
01 / 一文での本質
1-indexed 配列で、各セルは「そのセルを右端とする、長さが 2 のべき乗」の区間和を保持する —その長さは添字の最下位ビット。 点更新は暗黙の木を上へ歩く(最下位ビットを足す)、前缀和は下へ歩く(最下位ビットを引く)。 どちらも O(log N)、10 行のコード、明示的な木を割り当てる必要なし。
問題累積和 + 一点更新入力[3,2,-1,6,5,4,-3,3]更新arr[5] += 10クエリ[2,7]
長さ 8 の 1-indexed 配列。フェンウィック木 bit[i] は i で終わる lowbit(i) セル分の和を保持する。
ステップ
0 / 22
フェーズ
構築
現在
—
0 / 22
02 / パターンの骨格
# 1-indexed、長さ Ndef lowbit(i): return i & -i# 点更新:arr[i] += deltadef update(i, delta):while i ≤ N:bit[i] += deltai += lowbit(i)# arr[1..i] の前缀和def prefix(i):s ← 0while i > 0:s += bit[i]; i −= lowbit(i)return s# 区間和 [l..r] = prefix(r) − prefix(l − 1)
03 / このパターンを使うべき合図
「区間和 + 点更新」
典型的なユースケース。セグメント木と同じ問題クラスだが、BIT の方が短く、定数が小さく、 メモリも半分。集約が「和」やその他の逆元を持つ演算なら、まず BIT を選ぶ。
「転倒数 / それより小さいものの個数 / 座標圧縮」
配列を走査し、関心のあるキーを座標圧縮して小さな添字空間に押し込め、頻度 BIT を保持する。 各新要素が挿入前に「これまでに見た範囲に幾つあったか」を前缀数で問う。 LC 315、493、327 — どれも同じレシピ。
「区間更新 + 点クエリ」
差分配列に対する BIT。
update(l, +δ)、 update(r+1, −δ)、その後 prefix(i) が i の値を返す。 点クエリで足りる場面では遅延伝播付きセグメント木を置き換えられる。「2 次元 BIT で部分矩形和」
while ループを 2 重(次元ごとに 1 つ)にすれば、「可変グリッド上の部分矩形和」が O(log² N) で取れる。LC 308。
04 / よくある落とし穴
i.
0-indexed と 1-indexed の混同。
BIT は本来1-indexed — 添字 0 には
lowbit が無く(ループが進まない)、 前缀クエリの再帰終端になっている。0 を正当な添字として使うと両方向の while が同時に壊れる。bit[0..N] を確保し、すべて 1 から始める。ii.
BIT で済むのにセグメント木を取り出す。
BIT は逆元のある集約(和、XOR、個数)に向く。min / max / gcd は逆元が無い — 「引いて戻す」ができない — のでセグメント木が必要。軽い道具で足りる時に重武器に頼らないこと。
iii.
区間更新の差分配列トリックを忘れる。
素朴な BIT は点更新 + 区間クエリしかできない。区間更新のために BIT を毎回作り直すのが典型的なミス。 正解は差分配列に BIT を張ること:
update(l, +δ); update(r+1, −δ)、 その後 prefix(i) が i の値を返す。1 回の呼び出しで 2 回の範囲更新、合計 O(log N)。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。