· 開発

Fenwick 木で区間和を求める：i & -i が選ぶ区間と O(log n) の根拠

Fenwick 木で i & -i が各セルの区間を決める仕組みを、要素 8 個の例で更新と累積和のループとともに追い、インデックスの規則・構築コスト・オーバーフロー・セグメント木との違いを整理しました。

開発アルゴリズムデータ構造

配列 a の要素を頻繁に書き換えながら、a[l] + … + a[r-1] も何度も問い合わせたい場面があります。累積和の配列を前もって作っておけば問い合わせは O(1) ですが、要素を 1 つ変えるたびにそれ以降の累積和をすべて直す必要があり、更新は O(n) です。逆に配列だけを持っていれば更新は O(1)、問い合わせは O(n) です。

Fenwick 木（Binary Indexed Tree、BIT）は両方の操作を O(log n) にそろえます。記憶領域は長さ n の配列 1 本だけです。この記事では AtCoder Library（ACL）の fenwick_tree のドキュメントと実装を基準に、各セルがどの区間の和を持っているのか、2 つのループがなぜそのセルだけを訪れるのかを小さな例で追います。

出発点：累積度数表

名前の由来は、Peter M. Fenwick が 1994 年に Software: Practice and Experience 24 巻 3 号（327–336 ページ）に発表した論文 “A new data structure for cumulative frequency tables” です。Crossref に登録された出版社の抄録によると、この論文は動的な算術符号化（arithmetic coding）で使う累積度数を管理する “binary indexed tree” を提示しています。累積度数を要素番号の 2 進表現と対応する部分に分け、走査も番号の 2 進符号に沿って進む、という説明が抄録にあります。

ただし、この記事を書くにあたって確認できたのは Crossref の書誌情報と抄録までです。Wiley の論文本文は開けず、OpenAlex にも公開された全文は登録されていませんでした。以下の動作の説明は ACL のドキュメントとソースコードに基づくもので、元論文の証明や記法を引き写したものではありません。

ACL の公開 API

ACL のドキュメントが定めるインターフェースは次のとおりです。

呼び出し 意味 制約 計算量
fenwick_tree<T> fw(n) 0 で初期化された要素 n 個 O(n)
fw.add(p, x) a[p] += x 0 ≤ p < n O(log n)
fw.sum(l, r) a[l] + … + a[r-1] 0 ≤ l ≤ r ≤ n O(log n)

公開インデックスは 0-based で、区間は半開区間 [l, r) です。一方、内部のループは 1-based の番号で回ります。この 2 つの規則を混ぜるとほとんどのバグが生まれるので、この記事では公開位置を p、内部番号を i（= p + 1）と書き分けます。

ACL のソースと同じ構造で書き直すと次のようになります。ACL は値の型をテンプレート T で受け取りますが、ここでは読みやすさのため long long に固定しました。

struct Fenwick {
    int n;
    std::vector<long long> data;  // data[i-1]: 内部番号 i が受け持つ区間の和

    explicit Fenwick(int n) : n(n), data(n, 0) {}

    void add(int p, long long x) {             // a[p] += x
        for (int i = p + 1; i <= n; i += i & -i) data[i - 1] += x;
    }
    long long prefix(int r) const {            // a[0] + ... + a[r-1]
        long long s = 0;
        for (int i = r; i > 0; i -= i & -i) s += data[i - 1];
        return s;
    }
    long long sum(int l, int r) const {        // a[l] + ... + a[r-1]
        return prefix(r) - prefix(l);
    }
};

ACL の add も p を 1 増やしてから、p <= n の間 data[p-1] に加えて p += p & -p で次へ進みます。内部の累積和は r > 0 の間 data[r-1] を足し、r -= r & -r で r を減らします。公開の sum(l, r) は内部の累積和 2 つの差です。

i & -i：最下位の 1 ビット

2 の補数では -i は ~i + 1 です。i の最下位の 1 ビットより下はすべて 0 なので、ビットを反転するとそこがすべて 1 になり、1 を足すと繰り上がりがちょうどその 1 ビットの位置で止まります。その結果、i と -i の両方で 1 になっているビットは最下位の 1 ビットだけになります。

i      = 6 = 0110
-i         = 1010   (下位 4 ビット)
i & -i     = 0010 = 2

この値を lowbit(i) と呼ぶことにします。内部番号 i のセルは内部番号 (i - lowbit(i), i]、公開インデックスでいえば [i - lowbit(i), i) の和を持っています。奇数番号は自分の要素 1 つだけ、2 のべき乗の番号は先頭から自分までの全体を受け持ちます。内部番号 0 は使いません。0 & -0 は 0 なので、0 から始めたループは終わらないからです。ACL の add が最初に p を 1 増やすのもこのためです。

要素 8 個で追ってみる

公開配列を a = [5, 2, 9, -3, 4, 0, 7, 1]（0-based）とし、セルごとに受け持つ区間と値を書くと次のようになります。

内部 i 2 進 lowbit 公開区間 data[i-1]
1 0001 1 [0, 1) 5
2 0010 2 [0, 2) 7
3 0011 1 [2, 3) 9
4 0100 4 [0, 4) 13
5 0101 1 [4, 5) 4
6 0110 2 [4, 6) 4
7 0111 1 [6, 7) 7
8 1000 8 [0, 8) 25

累積和 prefix(7)（= a[0] + … + a[6]）:

i 足すセル 区間 累計 次の i
7 (0111) data[6] = 7 [6, 7) 7 7 − 1 = 6
6 (0110) data[5] = 4 [4, 6) 11 6 − 2 = 4
4 (0100) data[3] = 13 [0, 4) 24 4 − 4 = 0

区間 [6,7)、[4,6)、[0,4) は重ならずにつながり、ちょうど [0,7) を覆います。最下位の 1 ビットを 1 つずつ消すことは、[0, r) の右端からブロックを 1 つずつ切り取っていくことと同じです。直接計算した 5 + 2 + 9 − 3 + 4 + 0 + 7 = 24 と一致します。

区間和 sum(2, 7)：prefix(2) は i = 2 で data[1] = 7 を足してすぐ終わるので 7 です。よって 24 − 7 = 17 で、実際に 9 − 3 + 4 + 0 + 7 = 17 です。

更新 add(2, +10)：公開位置 2 は内部番号 3 です。

i 書き換えるセル 区間 次の i
3 (0011) data[2]: 9 → 19 [2, 3) 3 + 1 = 4
4 (0100) data[3]: 13 → 23 [0, 4) 4 + 4 = 8
8 (1000) data[7]: 25 → 35 [0, 8) 8 + 8 = 16 > 8、終了

表のうち公開インデックス 2 を含む区間を持つのは i = 3, 4, 8 の 3 つだけで、ループはちょうどそのセルを訪れました。lowbit を足すと繰り上がりが起きて次の番号の lowbit がより上の桁に上がり、そのセルは今のセルの区間を含むより広い区間を受け持ちます。更新後の prefix(7) は data[6] + data[5] + data[3] = 7 + 4 + 23 = 34 で、先ほどの 24 から 10 増えています。

計算量

  • 累積和：反復のたびに i の 1 ビットが 1 つ消えます。反復回数は r の 1 ビットの数で、r ≤ n なので ⌊log₂ n⌋ + 1 を超えません。
  • 更新：i に lowbit(i) を足すと、次の番号の lowbit は少なくとも 2 倍になります。n を超えたら止まるので、反復は ⌊log₂ n⌋ + 1 回以下です。
  • 区間和：累積和 2 回なので O(log n) です。
  • 領域：長さ n の配列 1 本で O(n) です。

この解析は上のループから導いた説明で、結論は ACL のドキュメントにある O(log n) と一致します。

初期値があるときの構築コスト

ACL のコンストラクタの O(n) は、すべての要素が 0 の構造を作るコストです。任意の初期配列を入れるために add を n 回呼ぶと O(n log n) になります。

線形時間で構築する方法もあります。ACL の API にはないので自分で実装します。data を a で埋めたあと、i = 1 から n まで順に、自分の値を親のセル i + lowbit(i)（n 以下のとき）に足します。

for (int i = 1; i <= n; i++) data[i - 1] = a[i - 1];
for (int i = 1; i <= n; i++) {
    int j = i + (i & -i);
    if (j <= n) data[j - 1] += data[i - 1];
}

i に値を送るのは i より小さい番号だけなので、i を処理する時点で data[i-1] はすでに完成しています。上の a に適用すると [5, 7, 9, 13, 4, 4, 7, 25] となり、表と同じ値になります。

間違えやすいところ

  • 空区間：sum(l, l) は prefix(l) - prefix(l) なので 0 です。ACL の制約も l == r を許しています。
  • 範囲：ACL のドキュメントの制約は 0 ≤ p < n、0 ≤ l ≤ r ≤ n です。自分で実装するとき、内部番号 0 を更新ループに入れると終わらなくなります。
  • 負の変化量：和であれば add(p, -x) でそのまま引けます。
  • 値の代入：Fenwick 木は a[p] を別に保持していません。a[p] = v をするには元の値が必要なので、元の配列を一緒に持って add(p, v - a[p]) とするか、sum(p, p + 1) で O(log n) で現在の値を復元します。
  • オーバーフロー：和の絶対値は最大で n × max|a[i]| になります。n = 2×10⁵、|a[i]| ≤ 10⁹ なら 2×10¹⁴ で 32 ビット整数を超えるので、64 ビットが必要です。ACL のドキュメントには、整数型でオーバーフローした場合は答えを 2^bit で割った余りで返すと書かれています。自分で実装する場合、C++ の符号付き整数のオーバーフローは未定義動作なので、最初から十分な幅の型を選んでください。詳しくは整数オーバーフローの記事にあります。

ほかのデータ構造との比較

問い合わせ 一点更新 メモリ
累積和の配列 O(1) O(n) n + 1
Fenwick 木 O(log n) O(log n) n
セグメント木 O(log n) O(log n) 通常 n より多いノード

更新がなければ累積和の配列のほうが単純で速いです。セグメント木も一点更新と区間の問い合わせを O(log n) で処理でき、最小値・最大値のように逆演算のない演算や、遅延伝播を使った区間更新まで扱えます。その代わり実装と記憶領域が大きくなります。Fenwick 木があらゆる場合にセグメント木より速いと言い切る根拠はなく、実際の差は実装と負荷ごとに測る必要があります。

Fenwick 木の区間和は prefix(r) - prefix(l) という引き算に頼っています。足し算のように逆元のある演算でなければこの方法は使えません。最大値は結合法則を満たしますが、引き算で前の部分を消せないので、任意の区間 [l, r) の最大値は同じ方法では得られません。値が増える一方で累積の最大値だけを問う場合のように条件を付けた変形はありますが、この記事の範囲は整数の和までです。

使いどころ：再び累積度数

抄録が述べる本来の用途と同じく、記号 0…n−1 の出現回数を数えるのにそのまま使えます。記号 s が出るたびに add(s, 1)、s より小さい記号の累積度数は sum(0, s) です。同じやり方で「これまでに見た値のうち x 以下はいくつか」を値の範囲上で数えれば、転倒数（inversion count）のような問題も O(n log n) で解けます。値の範囲が大きければ、座標圧縮で先に 0…k−1 に対応させます。

確認した資料

すべて 2026-10-27 に確認しました。

ブログへ