- Fenwick Tree（Binary Indexed Tree）は、配列の一点更新と区間和クエリをどちらも O(log n) で処理できるデータ構造です。
- 素の配列では更新が O(1)・区間和が O(n)、累積和配列では逆になるのに対し、Fenwick Tree は両者をバランスよく扱えます。
- インデックスの最下位ビット（lsb）を使って担当範囲を決め、更新時は lsb を足して上位へ伝播し、クエリ時は lsb を引きながら合計を積み上げます。
1. どんな問題を解くか
配列の区間和を繰り返し求めながら、途中で値を更新する。
この2つが重なる場面で、Fenwick Tree（Binary Indexed Tree、BIT）が使えます。
たとえば、次のような操作で区間和を求める問題を考えます。
問題
長さ N の整数列 A がある。Q 個の2種類のクエリを順に処理せよ。
1 i x→ A[i] に x を加える2 l r→ A[l] + A[l+1] + … + A[r] を出力する
制約: N, Q ≤ 100,000
たとえば A = (0 0 0 0 0) から始めて、5個のクエリを処理したとします。
1 3 7 → A[3] に 7 を加える → (0 0 7 0 0)
1 1 3 → A[1] に 3 を加える → (3 0 7 0 0)
2 1 3 → A[1]〜A[3] の和 → 10
1 4 5 → A[4] に 5 を加える → (3 0 7 5 0)
2 2 5 → A[2]〜A[5] の和 → 12Code language: CSS (css)1.1. 2分索引木と計算オーダー
この問題では、区間和をまとめるために毎回 reduce で走査すると、クエリ1回が O(N) になります。
すると、Q 個のクエリを処理する全体では O(N × Q) になります。
制約の最大のケース（N = Q = 100,000 のとき）では、単純計算で100億回の操作になります。
これを、O(Q log N)、 約170万回の操作で処理できるのが、2分索引木のアルゴリズムです。
「2分索引木（Binary Indexed Tree）」は、「二進数のビット構造をインデックスとして使う木」という意味です。
BIT、あるいは考案者にちなんで Fenwick Tree とも呼ばれます。
この方法のポイントは、値の更新（1のクエリ）と区間和の計算（2のクエリ）をバランスよく分けることです。
| 方法 | 更新 | 区間クエリ |
|---|---|---|
| 素の配列 | O(1) | O(n) |
| 累積和配列 | O(n) | O(1) |
| Fenwick Tree | O(log n) | O(log n) |
もし、更新がない問題なら累積和配列が有効です。
しかし、更新とクエリが混在する場合には、累積和配列では更新処理に時間がかかってしまいます。
1.2. 繰り返し二乗法
Fenwick Tree の発想の根っこにあるのは、繰り返し二乗法の考え方です。
たとえば、a^13 を計算するとき、13回掛け算するのは大変です。
;; n回掛け算する素直な実装
(defun power-naive (a n)
(let ((result 1))
(dotimes (_ n result)
(setf result (* result a)))))Code language: JavaScript (javascript)そこで、13を以下のように分解します。
13 = 1101₂ = 8 + 4 + 1
a^13 = a^8 × a^4 × a^1たとえば、a^8は、a^2^2^2なので 3 回の計算で済みます。
つまり、二進数で表したときにビットが立っている桁だけ処理すれば、O(n) だった計算が O(log n) になります。
;; 二進数分解で log n 回に抑える実装
(defun power-fast (a n)
(let ((result 1))
(loop while (> n 0)
do (when (logbitp 0 n) ; 最下位ビットが1なら掛ける
(setf result (* result a)))
(setf a (* a a)) ; a → a² → a⁴ → ...
(setf n (ash n -1))) ; n >>= 1
result))Code language: JavaScript (javascript)たとえば、2^10000（3011桁の整数）を500回計算した速度を計測してみると、
naive: 84802.8 ms （約85秒）
fast: 163.1 ms
ratio: 520x 高速Code language: HTTP (http)N が大きくなるほど効率の差が出てきます。
1.3. 区間和の分解
区間和でも同じ考え方ができます。
たとえば、数列 A_1 〜 A_7 までの合計を sum(1..7) とします。
すると、この計算は 7回足す代わりに、3つのブロックに分解できます。
7 = 111₂ = 4 + 2 + 1
sum(A_1..A_7) = sum(A_1..A_4) + sum(A_5..A_6) + sum(A_7..A_7)
| [========4========] [===6===] [7]
+---+----+----+----+----+----+----+----+
A_n 1 2 3 4 5 6 7 8あらかじめ各ブロックの区間和を用意しておけば、任意の区間和を少ない足し算で計算できます。
2. Fenwick Treeを作る
では、どのようにブロックの合計を用意すればよいのでしょう。
Fenwick Tree では、通常の配列を1本使います。
これを 配列 tree とし、N個分まで入るように確保します。
各インデックスが「何要素分の和を担当するか」を決めます。
たとえば、8つの数列の場合には、
index 個数 担当する要素
tree[1] 1 sum[1..1]
tree[2] 2 sum[1..2]
tree[3] 1 sum[3..3]
tree[4] 4 sum[1..4]
tree[5] 1 sum[5..5]
tree[6] 2 sum[5..6]
tree[7] 1 sum[7..7]
tree[8] 8 sum[1..8]Code language: CSS (css)treeの各要素のカバーしている範囲を図示すると、
8 | [==================8==================]
4 | [========4========]
2 | [===2===] [===6===]
1 | [1] [3] [5] [7]
+---+----+----+----+----+----+----+----+
1 2 3 4 5 6 7 8このように分解しておけば、sum(1..7)は、
A[1]+A[2]+…+A[7] としなくても、
treeの要素のカバーしている領域から、
tree[4]+tree[6]+tree[7] を足せばよいことになります。
Fenwick Tree はこの「2の累乗単位への分解」を配列のインデックスに直接埋め込んだデータ構造です。
2.1. Fenwick Tree
Fenwick Treeのインデックス i の要素が担当するA_n要素数は、2で何回割れるかで決まります。
index: 1 2 3 4 5 6 7 8
担当個数: [1] [2] [1] [4] [1] [2] [1] [8]Code language: CSS (css)たとえば、
tree[4]は、A_1〜A_4の 4要素分を担当し、
tree[6]は、A_5〜A_6の 2要素分を担当し、
tree[8]は、要素A_1〜A_8の全体を担当します。
これは、i の最下位セットビット（lowest set bit）から求まります。
(defun lsb (i)
(logand i (- i)))
(lsb 6) ;=> 2 （6 = 110₂ → 最下位ビットは 10₂ = 2）
(lsb 4) ;=> 4 （4 = 100₂ → 最下位ビットは 100₂ = 4）
(lsb 7) ;=> 1 （7 = 111₂ → 最下位ビットは 1₂ = 1）Code language: PHP (php)i の担当範囲は [i - lsb(i) + 1 .. i] です。
2.2. 更新の伝播
さて、A[3] に 7 を足す場合、その担当しているすべての要素を更新する必要があります。
A[3]を担当しているのは、tree[3]と tree[4]と tree[8]と…、
8 | [......+7.....................]
4 | [......+7....]
2 |
1 | [+7]
1 2 3 4 5 6 7 8
↑ 更新起点つまり、このように3箇所に値を加算します。
index: 0 1 2 3 4 5 6 7 8
tree : 0 0 0 7 7 0 0 0 7これは、indexにlsb(i) を足しながら上へ伝播していきます。
たとえば、3 の次の 4 を探すには、 3 + lsb(3) を計算すればよいわけです。
step 1: tree[3] += 7 (3 = 011₂, lsb=1)
step 2: 3+1=4, tree[4] += 7 (4 = 100₂, lsb=4)
step 3: 4+4=8, tree[8] += 7 (8 = 1000₂, lsb=8)2.3. クエリの積み上げ：sum(1..5)
逆に、クエリに対して合計を計算するには、担当ブロックを探して足します。
ブロックが重ならず、かつ隙間なく 1..i を覆うのがポイントです。
たとえば、sum(1..5)なら、tree[5]+tree[4] です。
4 | [====tree[4]====]
1 | [tree[5]]
1 2 3 4 5
合計 = tree[4] + tree[5]
= sum(1..4) + A[5] = sum(1..5) ✓5 → 4 → 0（終了）と進むのは、元の数に lsb(i) を引きながら繰り返していることになります。
step 1: sum += tree[5] (5=101₂, lsb=1, 担当[5..5])
step 2: 5-1=4, sum += tree[4] (4=100₂, lsb=4, 担当[1..4])
step 3: 4-4=0, ループ終了3. Fenwik Tree のCommon Lisp 実装
それでは、Fenwik Tree をCommon Lispで実装していきます。
まず、配列を作ります。
;; サイズ n の Fenwick Tree を作る（1-indexed）
(defun make-fenwick (n)
(make-array (1+ n) :initial-element 0))Code language: CSS (css)配列のサイズを n+1 にしているのは、インデックスを1始まりにするためです。aref tree 0 は使いません。
3.1. 一点更新（fenwick-update! ）
A_i に delta を加えた場合、tree の該当する要素を更新していきます。
ループ変数 i は、 lsb(i) を足しながら、終端を超えるまで上位へ伝播しています。
(defun fenwick-update! (tree i delta)
(loop while (<= i (1- (length tree)))
do (incf (aref tree i) delta)
(setf i (+ i (lsb i)))))Code language: JavaScript (javascript)たとえば、i = 3 で更新すると、3 → 4 → 8 と進みます。
A_3 を 7 増やした場合は、
(let ((tree (make-fenwick 8)))
(fenwick-update! tree 3 7)
tree)
;=> #(0 0 0 7 7 0 0 0 7)Code language: PHP (php)インデックス3と、3を担当範囲に含む4・8にも 7 が反映されています。
3.2. 累積和クエリ（fenwick-query）
反対に、sum(1..i)を計算するには、反対方向の合計を取ります。
(defun fenwick-query (tree i)
(let ((sum 0))
(loop while (> i 0)
do (incf sum (aref tree i))
(setf i (- i (lsb i))))
sum))Code language: JavaScript (javascript)i から lsb(i) を引きながら担当範囲を剥がして合計を積み上げます。
(let ((tree (make-fenwick 8)))
(fenwick-update! tree 1 3)
(fenwick-update! tree 3 7)
(fenwick-update! tree 5 2)
(fenwick-query tree 5))
;=> 12 （index 1〜5 の和: 3 + 0 + 7 + 0 + 2）Code language: JavaScript (javascript)3.3. 区間和クエリ（fenwick-range）
区間 [l, r] の和を求めるには、
右までの区間[1, r]の累積和から、
左までの区間 [1, l-1] の累積和を引けばよいことになります。
(defun fenwick-range (tree l r)
(- (fenwick-query tree r)
(fenwick-query tree (1- l))))3.4. まとめて使う
冒頭の問題を解くのに、Fenwick Treeを使ってみます。
リスト queries を一つずつ type と args に分けて、ecaseで分岐します。
(defun solve (n queries)
(let ((tree (make-fenwick n)))
(loop for (type . args) in queries
do (ecase type
(1 (fenwick-update! tree (first args) (second args)))
(2 (print (fenwick-range tree (first args) (second args))))))))Code language: Lisp (lisp)問題を与えると、クエリに対応した回答が出てきます。
(solve 8
'((1 1 3) ; index 1 に +3
(1 3 7) ; index 3 に +7
(1 5 2) ; index 5 に +2
(2 1 5) ; index 1〜5 の和
(2 3 6))) ; index 3〜6 の和
;=> 12
;=> 7Code language: Lisp (lisp)4. 【応用】動的な集合の k 番目に小さい値を求める
Fenwick Tree では配列の区間和を計算するだけでなく、順位探索という全く別の用途に転用できます1。
使う操作は fenwick-update! と fenwick-query だけで、読み替えによって、「集合に要素を追加しながら、k 番目に小さい値を高速に問い合わせる」という問題にも使えます。
4.1. 問題設定
次のようなクエリ列を処理したいとします。
値の範囲は 1 以上 M 以下とします。
add 5 → 集合 S に 5 を追加する
add 2 → 集合 S に 2 を追加する
add 7 → 集合 S に 7 を追加する
kth 2 → S の中で小さい順に 2 番目の値を返す → 5
add 1 → 集合 S に 1 を追加する
kth 1 → S の中で小さい順に 1 番目の値を返す → 1素朴な実装では、add のたびにソート済みリストに挿入し、kth は先頭から数えます。
(defun solve-kth-queries/naive (M queries)
"M: 値の範囲の上限（1..M）
queries: (add v) または (kth k) のリスト"
(let ((sorted-list '()))
(loop for (type arg) in queries
collect (ecase type
(add
(setf sorted-list
(merge 'list sorted-list (list arg) #'<))
nil)
(kth
(nth (1- arg) sorted-list))))))Code language: Lisp (lisp)挿入は O(N)、クエリは O(1) ですが、クエリが多い場合でも add の重さが効いてきます2。
4.2. 累積和を「個数カウンタ」として読み替える
Fenwick Tree を使うと、どちらの操作も O(log M) になります。
通常の用途では、配列の値そのもの（3, 7, 2 など）をFenwick Tree に入れていました。
ここでは、「値 v が集合 S に含まれているなら 1、含まれていないなら 0」を入れます。
たとえば M=8 で、集合が {2, 5, 7} のとき、頭の中にある元配列は次のようになります。
index: 1 2 3 4 5 6 7 8
値: 0 1 0 0 1 0 1 0Code language: HTTP (http)つまり、 番に を加算する、という操作を
番に $1$ をカウントする、という操作に置き換えればよいです。
この 0/1 配列に対して fenwick-query で累積和を計算すると、「x 以下に何個の要素があるか」という個数になっています3。
fenwick-query(tree, 1) = 0 → 1 以下に 0 個
fenwick-query(tree, 2) = 1 → 2 以下に 1 個
fenwick-query(tree, 5) = 2 → 5 以下に 2 個
fenwick-query(tree, 7) = 3 → 7 以下に 3 個つまり、fenwick-query(tree, x)は、「区間の合計」ではなく「個数カウンタ」として動いています。
index: 1 2 3 4 5 6 7 8
値: 0 1 0 0 1 0 1 0
tree[x] 0 1 1 1 2 2 3 3
↑ ↑ ↑Code language: CSS (css)5. k 番目に小さい値は lower_bound で求まる
個数カウンタとして読めるようになったので、次は順位探索を考えます。
「k 番目に小さい値」は、「累積個数が初めて k 以上になる最小の index」と言い替えられます。
fenwick-query(tree, x) は x が大きくなるにつれて単調に増加するたらで、lower_bound（下限探索）と同じ構造になります。
先ほどの例（集合 {2, 5, 7}）で確認します。
index x: 1 2 3 4 5 6 7 8
個数: 0 1 1 1 2 2 3 3- 1 番目に小さい値 → 個数が初めて 1 以上になる最小 index → 2
- 2 番目に小さい値 → 個数が初めて 2 以上になる最小 index → 5
- 3 番目に小さい値 → 個数が初めて 3 以上になる最小 index → 7
ソートした結果 [2, 5, 7] の 1 番目・2 番目・3 番目と一致しています。
5.1. 実装（1）：二分探索版 O(log² M)
まず理解しやすい実装として、fenwick-query を呼びながら二分探索する版を書きます。
(defun fenwick-kth/binary-search (tree k)
"k 番目に小さい値を返す（1-indexed）。O(log^2 M)。"
(let ((lo 1)
(hi (1- (length tree))))
(loop while (< lo hi)
do (let* ((mid (floor (+ lo hi) 2))
(cnt (fenwick-query tree mid)))
(if (< cnt k)
(setf lo (1+ mid))
(setf hi mid))))
lo))Code language: Lisp (lisp)lo と hi で値の範囲を絞り込み、中点での個数が k 未満なら左半分を捨て、k 以上なら右半分を捨てます。
たとえば、集合 {2, 5, 7}（M=8）で k=2 を探すと、
lo=1, hi=8 → mid=4, 個数=1 < 2 → lo=5
lo=5, hi=8 → mid=6, 個数=2 >= 2 → hi=6
lo=5, hi=6 → mid=5, 個数=2 >= 2 → hi=5
lo=5, hi=5 → 終了 → 5Code language: HTML, XML (xml)正しく 5 が返ります。
fenwick-query が O(log M) で、ループも O(log M) 回回るので、全体は O(log² M) です4。
概念の確認には十分ですが、もう一段速くできます。
5.2. 実装（2）：binary liftingを使う O(log M) 版
Fenwick Tree の add と query が O(log M) で動く理由を思い出してください。
index を二進数として読み、最下位ビット lsb(i) を足す・引くことで、
担当範囲をビット単位で辿っていました。
この構造を逆に利用すると、二分探索なしで k 番目を O(log M) で求められます。
たとえば、M=8（3ビット）の場合、答えは 1〜8 のどこかです。
厳密にmidを取らずとも、最上位ビットから見て「左半分か右半分か」を比べていけば、log M 回で答えが確定します。
「2の冪乗ずつ」決め打ちで進むことで、「答えの index を上位ビットから 1 ビットずつ確定していく」というやり方になります。
というのも、x が2の冪乗なら、tree[x] は、担当している範囲の合計をそのまま持っています。
たとえば M=8 なら、
tree[4] → sum(1..4) の合計（左半分）
tree[8] → sum(1..8) の合計（全体）Code language: CSS (css)tree[4] の値を見るだけで、「1〜4 に何個あるか」が O(1) で分かります。fenwick-query(tree, 4) は tree[4] を 1 回だけ読めば済むからです（4 = 100₂ で lsb=4、すぐ 0 になる）。
5.3. ビットを上から確定する手順
変数 x を 0 で初期化し、残り個数 remain を k で初期化します。
M の最上位ビットから始めて、各ステップで次を繰り返します。
next = x + bit （今見ているビットを加えた候補）
集合 {2, 5, 7}、M=8、k=2 の場合
bit=4: next=4, tree[4]=1, remain=2 → 1 < 2 なので x=4, remain=1
bit=2: next=6, tree[6]=1, remain=1 → 1 >= 1 なので x は動かない
bit=1: next=5, tree[5]=1, remain=1 → 1 >= 1 なので x は動かない
→ x+1 = 5Code language: HTML, XML (xml)もし next <= M かつ tree[next] < remain なら、答えは next より右にあります。
右の範囲のremain を見るには tree[next] を引き、x を next に進めます。
そうでなければ、答えは next 以下にあるので、x を動かしません。
全ビットを処理し終えたとき、x + 1 が答えです5。
3回の比較で 5 が求まります。
5.4. 実装（fenwick-kth）
(defun fenwick-kth (tree k)
"k 番目に小さい値を返す（1-indexed）。O(log M)。"
(let ((n (1- (length tree))))
(loop with x = 0
with remain = k
for bit = (ash 1 (1- (integer-length n))) then (ash bit -1)
while (> bit 0)
do (let ((next (+ x bit)))
(when (and (<= next n)
(< (aref tree next) remain))
(decf remain (aref tree next))
(setf x next)))
finally (return (1+ x))))) Code language: Lisp (lisp)integer-length は整数のビット幅（二進数で何桁か）を返す Common Lisp の組み込み関数です6。n=8 なら integer-length は 4 を返し、(ash 1 3) で bit=8 から始まります。
二分探索版と同じ結果になることを確認します。
(let ((tree (make-fenwick 8)))
(fenwick-update! tree 2 1)
(fenwick-update! tree 5 1)
(fenwick-update! tree 7 1)
(list (fenwick-kth tree 1)
(fenwick-kth tree 2)
(fenwick-kth tree 3)))
;=> (2 5 7)Code language: Lisp (lisp)6. Peter Fenwick と発案の経緯
Fenwick Treeは、1994年に Peter Fenwick が論文 “A new data structure for cumulative frequency tables” で発表したデータ構造です。
元々の動機は情報圧縮での符号長計算です。
頻度表の累積和を効率よく更新する問題を解くために考えられました。
Binary Indexed Tree という別名は、構造の本質をよく表しています。
配列のインデックスを二進数として読み、そのビット構造をそのまま木として利用しているからです。
Fenwick Treeの面白いところは、配列が木構造として動作すること。
余分な木構造や左右のポインタが不要になります。
「2の累乗への分解」という発想のおかげで、通常の配列1本だけで完結します。
6.1. セグメント木との違い
ただし、Fenwick Tree は「区間和」と「一点更新」の組み合わせに特化したデータ構造です。
「区間の最大値」や「区間ごとに値を加算する」といった操作には対応していません。
そういう用途であれば、セグメント木を使います。
Fenwick Tree の優位性は、実装の行数が半分以下で、処理も軽いことです。
もし、区間和だけで解ける問題なら Fenwick Tree を選ぶほうが自然です。
6.2. 全コード
(defun lsb (i)
(logand i (- i)))
(defun make-fenwick (n)
(make-array (1+ n) :initial-element 0))
(defun fenwick-update! (tree i delta)
(loop while (<= i (1- (length tree)))
do (incf (aref tree i) delta)
(setf i (+ i (lsb i)))))
(defun fenwick-query (tree i)
(let ((sum 0))
(loop while (> i 0)
do (incf sum (aref tree i))
(setf i (- i (lsb i))))
sum))
(defun fenwick-range (tree l r)
(- (fenwick-query tree r)
(fenwick-query tree (1- l))))
(defun fenwick-kth (tree k)
"k 番目に小さい値を返す（1-indexed）。O(log M)。"
(let ((n (1- (length tree))))
(loop with x = 0
with remain = k
for bit = (ash 1 (1- (integer-length n))) then (ash bit -1)
while (> bit 0)
do (let ((next (+ x bit)))
(when (and (<= next n)
(< (aref tree next) remain))
(decf remain (aref tree next))
(setf x next)))
finally (return (1+ x))))) Code language: Lisp (lisp)- この応用は「Order Statistics Tree using BIT」として競技プログラミングの文脈でよく知られています。 – Order statistic tree using fenwick tree (BIT) – GeeksforGeeks
- ソート済み配列への挿入は、挿入位置の特定が O(log N) でも、要素のシフトが O(N) かかるため全体は O(N) になります。 – Order statistic tree using fenwick tree (BIT) – GeeksforGeeks
- Fenwick Tree の一点更新と prefix sum の仕組みについては cp-algorithms の解説が詳しいです。 – Fenwick Tree – Algorithms for Competitive Programming
- この二分探索版は Codeforces の解説でも「十分に速い（Good enough to get AC verdict）」と評価されています。 – A Gentle Introduction to Fenwick Trees – Codeforces
- このアルゴリズムは「binary lifting」とも呼ばれ、Fenwick Tree の内部構造を使って O(log N) で k 番目の要素を求める標準的な手法です。 – A Gentle Introduction to Fenwick Trees – Codeforces
(integer-length 8)は 4 を返します（8 = 1000₂ で 4 ビット）。ANSI Common Lisp 標準で定義されており、(ash 1 (1- (integer-length n)))で n の最上位ビットに相当する 2 の冪が得られます。 – Function INTEGER-LENGTH – Common Lisp HyperSpec