フェニック木

サムネイル|200x200ピクセル|配列[1, 2, 3, 4, 5]を順次挿入し、フェニック木を構築する様子フェニック木（フェニックぎ、）またはBinary Indexed Tree（BIT）とは、数列の先頭からの部分和の計算と要素の更新の両方を、ともに時間で行えるデータ構造である。「フェニック」は英語の発音に近い表記で、「フェンウィック木」「フェンウィック・ツリー」とも表記される。

ボリス・リャブコ（Boris Ryabko）が1989年に算術符号の高速な適応型符号化のために考案し、1992年に改良版を発表した。その後、1994年にピーター・フェニック（Peter M. Fenwick）がデータ圧縮における累積頻度表の管理手法として同じ構造を論文で解説したことから、フェニック木の名で広く知られるようになった。競技プログラミングでは、セグメント木より実装が短く定数倍も小さいことから、頻繁に用いられる。

概要値の列 A, …, A[n] に対して、素朴な実装には次の2通りがあるが、いずれも片方の操作が遅い。値そのものを配列に保存する場合、要素の更新はだが、部分和の計算にかかる。部分和（累積和）を配列に保存する場合、部分和の計算はで、探索もでできるが、1つの要素の更新で後続のすべての累積和を書き換える必要があり、かかる。

フェニック木は、値を n+1 個の節点からなる木として表現し、各節点に「親（の次の位置）から自分までの区間の和」を持たせることで、要素の更新・部分和の計算・部分和から位置への逆引き（順位探索）のすべてをで可能にする。空間量はであり、元の配列と同じ長さの配列1本で表現できる。

木構造は明示的なポインタを持たず、配列の添字にビット演算を施すことで親子関係を求めるとして実装される。

動機配列の各位置までの累積和（部分和）が、配列の値を更新しながら繰り返し必要になる場面がある。代表例が、算術符号の適応型符号化である。この符号化では、各記号の出現回数を数え続け、符号化のたびに「ある記号より小さい記号の出現回数の合計」、すなわち累積確率を求める必要がある。出現回数は1記号ごとに更新されるため、更新と部分和の計算の両方が高速なデータ構造が求められ、フェニック木が考案された。

構造添字の算術フェニック木は、1始まりの添字を持つ配列 A[1..n] に対し、同じ長さの配列 F[1..n] を持つ。添字の算術で重要になるのが、最下位の立っているビット（least significant set bit）である。これは i を割り切る最大の2の冪であり、と書く。例えば lsb(12) = lsb(11002) = 4 である。2の補数表現では、次のように1命令で求められる。

配列 F の各要素は、A の末尾が i である、長さ lsb(i) の区間の和を持つ。

例えば F = A+…+A、F = A+A、F = A である。i が奇数なら F[i] = A[i] であり、i が2の冪なら F[i] は先頭から i 番目までの和となる。区間は、添字を2進表記したときに下位の「1」のビットを基準に切り分けられる。

なお、0を根とする架空の節点が説明に用いられることがあるが、実際には参照されず、保存する必要もない。

実際には、フェニック木は同じ配列の上に定義される3つの暗黙の木、すなわち「問い合わせ木」「更新木」「探索木」を組み合わせたものとみなせる。前の2つは通常、葉から根へ向かって辿り、探索木は根から葉へ向かって辿る。

問い合わせ木サムネイル|right|300px|16節点（根を含む）の問い合わせ木。節点 i の親は i − lsb(i)。各節点は、親の次の位置から自分までの A の区間和を持つ。節点 i の親を i − lsb(i)（= i & (i−1)、最下位の「1」のビットを0にした値）と定めた木である。根は0。例えば6 = 1102 の親は 4 = 1002、さらにその親は0となる。

k 段目の節点は、2進表記で「1」のビットがちょうど k 個ある添字である。ビット数は高々なので、木の深さはである。

先頭からの部分和 A+…+A[i] は、i とその親、親の親…と根の直前まで遡り、各節点の F を足し合わせることで得られる。これは「i の2進表記の「1」のビットを下位から1つずつ落としながら足す」ことと同じである。

例えば最初の11要素の和を求める場合、11 = 10112 であるから、F[10112]（A）、F[10102]（A[9..10]）、F[10002]（A[1..8]）の3つを足せばよい。

サムネイル|center|600px|n = 16 の F が担当する区間（幅は lsb(i)）。先頭11要素の和は、青色の F、F、F の和で求まる。

更新木問い合わせ木と鏡像の関係にある木で、節点 i の親は i + lsb(i) である。例えば6 = 1102 の親は 8 = 10002 である。この木は本来無限に続くが、添字が n を超える節点は保存も参照もされない。

ある節点の祖先は、自分の担当区間を含む区間を担当する節点のすべてである。したがって A[i] を変更するには、F[i]、その親、親の親…と、添字が n を超えるまで変更量を加えればよい。

例えば n = 16 で A を更新する場合、更新が必要なのは F、F、F の3つである（11 = 10112 → 11002 → 100002）。

サムネイル|center|600px|A を更新するときに書き換える節点（橙色）。11を含む区間を担当する F、F、F に変更量を加える。

探索木探索木は、他の2つと異なり二分木であり、クヌースが「横向きのヒープ」（sideways heap）と呼ぶ配置になっている。各節点の高さを、添字の2進表記の末尾の0の個数と定め、隣接する高さの最も近い添字を親子とする。奇数の添字（lsb(i) = 1）は葉であり、偶数の添字 i の子は i ± lsb(i)/2 である。

左部分木は更新木での子孫、右部分木は問い合わせ木での子孫に対応する。この木は主に、部分和の値から位置を求める順位探索（後述）に用いられる。

操作以下、添字は1始まりとする。

部分和先頭から i 番目までの和は、問い合わせ木を辿って求める。

function prefix_sum(F, i) is s := 0 while i > 0 do s += F[i] i -= lsb(i) return s

反復回数は i の2進表記における「1」のビットの数以下なので、である。

区間和 A[l]+…+A[r] は prefix_sum(r) − prefix_sum(l−1) で求められる。2つの問い合わせ木上の経路は、最初の共通の祖先より上では同一の節点を通る。そのため、共通祖先に達した時点で打ち切ると、短い区間ほど少ない手数で済む。極端な例が1点の取得で、A[j] は F[j] から出発し、j − lsb(j) に達するまで F[i]（i = j−1 から lsb を引きながら遡る）を引くことで、A[j] の値を求められる。

計算量は、部分和の計算2回分であり、最悪でもである。1回の部分和で足す項数は、i の2進表記の「1」のビットの数以下なので、区間和全体では高々 2(+1) 項である。共通祖先で打ち切る場合、手数は l−1 と r の2進表記が分かれる最上位ビットより下のビット数に比例し、区間が2の冪の境界をまたがない短い区間では、定数回から回程度で済む。ただし区間が大きな2の冪の境界をまたぐ場合は、短い区間でもかかる。

更新 A[i] に x を加算するには、更新木を辿る。

function add(F, i, x) is while i <= n do F[i] += x i += lsb(i)

これもである。値を x に「書き換える」場合は、現在の値 A[i] を区間和として求め、その差分 x − A[i] を加算する。実用上は、元の配列を別に保持して差分を直接求めることも多い（メモリは2倍になる）。

構築空の木に n 個の値を1つずつ加算するとかかるが、次のようにすればで構築できる。

function construct(A) is F := A のコピー for i from 1 to n do j := i + lsb(i) if j <= n then F[j] += F[i] return F

各節点を、更新木での親に1度だけ足し込むという考え方である。

順位探索値がすべて非負の場合、部分和は単調非減少となる。このとき、「部分和が w 以上となる最小の添字」（下限、lower bound）を、探索木を根から降りることでで求められる。2分探索を各ステップで部分和の計算込みで行うとかかるが、フェニック木では F の値をそのまま比較に使えるため、1回の降下で済む。これは「2分探索の各ステップで、2の冪ずつ位置を進める」手法（binary lifting）としても知られる。

function lower_bound(F, w) is pos := 0 for step in (2^k, 2^(k-1), ..., 1) do // 2^k ≤ n を満たす最大の冪から始める if pos + step <= n and F[pos + step] < w then pos += step w -= F[pos] return pos + 1 // 存在しなければ n+1

頻度表に対しては、「累積確率から記号を逆引きする」復号処理にそのまま使える。

サムネイル|center|600px|探索木での順位探索の例。A = [2, 5, 6, 8, 1, 3, 9]（累積和は [2, 7, 13, 21, 22, 25, 34]）で、累積和が15以上となる最小の添字は4。根から F[i] ≥ w なら左（i を候補とする）、そうでなければ w −= F[i] として右へ進む。

実装例 Pythonによる、点加算と区間和（部分和）を扱う実装例を示す。内部の添字は1始まりである。

class FenwickTree: """Fenwick tree (binary indexed tree), 1-indexed."""

def __init__(self, values): self.n = len(values) self.tree = + list(values) for i in range(1, self.n + 1): # O(n) construction j = i + (i & -i) if j <= self.n: self.tree[j] += self.tree[i]

def add(self, i, x): """A[i] += x""" while i <= self.n: self.tree[i] += x i += i & -i

def prefix_sum(self, i): """A + ... + A[i]""" s = 0 while i > 0: s += self.tree[i] i -= i & -i return s

def range_sum(self, l, r): """A[l] + ... + A[r]""" return self.prefix_sum(r) - self.prefix_sum(l - 1)

def lower_bound(self, w): """Smallest i with prefix_sum(i) >= w (all values must be non-negative).""" pos = 0 step = 1 << self.n.bit_length() while step: nxt = pos + step if nxt <= self.n and self.tree[nxt] < w: pos = nxt w -= self.tree[nxt] step >>= 1 return pos + 1

使用例:

bit = FenwickTree([2, 5, 6, 8, 1, 3, 9]) bit.prefix_sum(4) # 21 (2 + 5 + 6 + 8) bit.add(4, 10) # A = 18 bit.range_sum(3, 5) # 25 (6 + 18 + 1)

C言語による実装と比較 C言語による実装例を示す。配列を線形に走査する素朴な方法と、同じ乱数列・同じ区間で区間和を計算して結果と実行時間を比較する。要素数が大きい場合、構築にかかる時間は配列への格納に比べて数割増える程度だが、その後の区間和の計算は大幅に高速になる。

#include <stdio.h> #include <stdlib.h> #include <time.h>

#define N (4 * 1024 * 1024) /* 要素数 */ #define MAX_VALUE 1024 /* 値は 0 以上 MAX_VALUE 未満 */ #define NQUERIES 1000 /* 区間和クエリの回数 */

typedef long long sum_t; /* N * (MAX_VALUE - 1) を保持できる型 */

/* 最下位の立っているビット。例: lsb(12) == 4 */ static size_t lsb(size_t i) { return i & -i; }

/* tree[1..n] に値が入っている状態から、その場でフェニック木に変換する (O(n)) */ static void fenwick_build(sum_t *tree, size_t n) { for (size_t i = 1; i <= n; i++) { size_t parent = i + lsb(i); if (parent <= n) tree[parent] += tree[i];

/* A[i] に delta を加える (O(log n)) */ static void fenwick_add(sum_t *tree, size_t n, size_t i, sum_t delta) { for (; i <= n; i += lsb(i)) tree[i] += delta; }

/* A + ... + A[i] を返す (O(log n)) */ static sum_t fenwick_prefix_sum(const sum_t *tree, size_t i) { sum_t sum = 0;

for (; i > 0; i -= lsb(i)) sum += tree[i]; return sum; }

/* A[l] + ... + A[r] を返す (O(log n)) */ static sum_t fenwick_range_sum(const sum_t *tree, size_t l, size_t r) { return fenwick_prefix_sum(tree, r) - fenwick_prefix_sum(tree, l - 1); }

/* 配列を線形に走査して A[l] + ... + A[r] を返す (O(r - l)、比較用) */ static sum_t flat_range_sum(const sum_t *a, size_t l, size_t r) { sum_t sum = 0;

for (size_t i = l; i <= r; i++) sum += a[i]; return sum; }

int main(void) { sum_t *a = calloc(N + 1, sizeof *a); sum_t *tree = calloc(N + 1, sizeof *tree); size_t (*queries) = malloc(NQUERIES * sizeof *queries); sum_t flat_total = 0, fenwick_total = 0;

if (!a || !tree || !queries) return EXIT_FAILURE;

/* 乱数列と、区間 [l, r] (1 <= l <= r <= N) を用意する */ srand((unsigned)time(NULL)); for (size_t i = 1; i <= N; i++) a[i] = tree[i] = rand() % MAX_VALUE; for (int q = 0; q < NQUERIES; q++) { size_t x = rand() % N + 1, y = rand() % N + 1;

queries[q] = x < y ? x : y; queries[q] = x < y ? y : x;

clock_t t0 = clock(); fenwick_build(tree, N); clock_t t1 = clock(); for (int q = 0; q < NQUERIES; q++) fenwick_total += fenwick_range_sum(tree, queries[q], queries[q]); clock_t t2 = clock(); for (int q = 0; q < NQUERIES; q++) flat_total += flat_range_sum(a, queries[q], queries[q]); clock_t t3 = clock();

printf("sum: fenwick=%lld flat=%lld (%s)\n", fenwick_total, flat_total, fenwick_total == flat_total ? "match" : "MISMATCH"); printf("fenwick build: %f s, queries: %f s\n", (double)(t1 - t0) / CLOCKS_PER_SEC, (double)(t2 - t1) / CLOCKS_PER_SEC); printf("flat queries: %f s\n", (double)(t3 - t2) / CLOCKS_PER_SEC);

free(queries); free(tree); free(a); return EXIT_SUCCESS; }

計算量構築: （逐次加算では）部分和・区間和・点更新・順位探索: 各空間量: （セグメント木は一般に 2n 程度の配列を要するが、フェニック木は n 個で済む）

制約と拡張演算と逆元フェニック木が扱えるのは、本質的には可換モノイドの演算による部分積である。部分和の計算と、値への加算（演算の適用）は、可換モノイドであれば可能である。

可換性は、点への加算に必要である。節点 F[j] は区間内の値を位置の順に演算した結果であり、A[i] に x を演算する更新を F[j] ← F[j] ⊕ x で行うと、x が区間の末尾に付くことになる。可換であれば、この順序の違いが結果に影響しないため成り立つ。可換でない演算では、更新のたびに該当節点を子の値から再計算する必要があり、更新がに悪化する。一方、構築と部分和の計算は、足す順序（添字の大きい節点が右側になるように）を守れば、可換でなくても行える。

逆元は、更新による「書き換え」（現在の値との差の加算）や、任意の区間 [l, r] に対する演算の計算に必要である。差を取るために演算の逆元が存在すること（アーベル群であること）が必要となる。実数の加算や、素数 p を法とする剰余環での加算などがこれにあたる。逆元の存在しない演算（最大値・最小値など）には、そのままでは区間クエリを適用できない。

最大値・最小値最大値・最小値のように逆元を持たない演算でも、「値を大きく（最小値なら小さく）する方向にしか更新できない」という制約のもとであれば、先頭からの区間の最大値・最小値をで求められる。さらに、通常の F に加えて、節点から右側の区間の最大値を持つ配列を併せて保持すると、先頭に限らず任意の区間 [L, R] の最大値もで求められる。更新で値を逆方向に変える必要がある場合は、セグメント木を用いる。

区間加算と点取得区間 [l, r] 全体に x を加算し、1点の値を取得するクエリは、差分列 D[i] = A[i] − A[i−1] をフェニック木で管理することで実現できる。区間加算は add(l, x) と add(r+1, −x) の2回の点加算に、点 i の値は prefix_sum(i) に対応する。

例えば A = [3, 1, 4, 1, 5, 9] の差分列は [3, −2, 3, −3, 4, 4] であり、A[2..5] に7を加えるには、D と D だけを更新すればよい。

区間加算と区間和区間への加算と区間の和を両方処理するには、2本のフェニック木 B1, B2 を用いる。差分列 D を用いると、先頭 i 番目までの和は次のように変形できる。

そこで、B1 には D[k]、B2 には k·D[k] を保持すれば、部分和は (i+1)·B1.prefix_sum(i) − B2.prefix_sum(i) で求められ、区間加算と区間和がともにで処理できる。メモリは通常の2倍となる。

サムネイル|center|600px|区間加算・区間和の例。[2, 5] に7を加えると、差分列 D は D と D だけが変わる。B1 に D[k]、B2 に k·D[k] を持たせ、累積和を (i+1)·ΣD[k] − Σk·D[k] で求める。

動的なフェニック木要素数 n が非常に大きく（例えば109）、実際に操作する位置が少ない場合は、配列の代わりに連想配列（ハッシュテーブル）に節点を持つことで、値が書き込まれた節点だけにメモリを割り当てられる。更新1回あたり高々個の節点しか作られないため、クエリを先読みできない場合でも座標圧縮（データの値の大小関係を保ったまま、より小さな自然数（0から始まる整数など）に置き換えるアルゴリズム）を使わずに処理できる。

多次元への拡張

添字ごとにフェニック木を入れ子にすることで、多次元配列に拡張できる。2次元の場合、点 (r, c) への加算は行方向の更新木と列方向の更新木を二重に辿り、矩形領域 [0, r)×[0, c) の和は二重の問い合わせ木の走査で求められる。任意の矩形 [r1, r2)×[c1, c2) の和は、包除原理により4つの矩形和の加減算で求まる。

（P(r, c) は原点からの矩形和）。1回の操作はで、3次元以上でも同様にで処理できる。また、区間加算・区間和の変種は、2次元で4本のフェニック木を用いることで実現でき、一般の d 次元では各操作を時間で行える。

サムネイル|center|600px|2次元の矩形和（包除原理）。原点からの矩形和 P を4回求めて、橙色の矩形 S の和を得る。灰色の領域は2回引かれるため、P(r1, c1) を足し戻す。

応用累積度数の管理算術符号など、記号の出現頻度を更新しながら累積頻度を求める符号化。フェニック木の本来の用途である。転倒数の計算数列を座標圧縮して1からnの整数に直し、後ろから順に見て、「すでに現れた値のうち、いまの値より小さいものの個数」を部分和として求め、その値を現れたものとして1点加算する。全体でで転倒数が求まる。順位統計量（k 番目に小さい値）値の取りうる範囲の各位置に、出現回数（0または1）を記録しておけば、集合への挿入・削除、「ある値が何番目に小さいか」、「k 番目に小さい値は何か」を、それぞれで処理できる。最後の問い合わせが順位探索（下限の探索）である。 2次元領域の和点の追加と矩形領域内の点の個数・値の和の問い合わせ。多次元への拡張を用いる。

他のデータ構造との比較セグメント木は、モノイドであれば逆元がなくても任意の区間の演算結果を求められ、区間更新の遅延評価も扱えるなど、汎用性が高い。一方、フェニック木は、扱える操作の範囲は狭いものの、実装が短く、必要メモリが少なく、定数倍も小さい。部分和の計算が主な用途で、逆元のある演算を扱う場合には、フェニック木が有利である。

脚注

フェニック木

Źródło i licencja