フェニック木とは

フェニック木（Fenwick tree / Binary Indexed Tree / BIT）とは、二進数の特性をうまく使って、ある範囲内の総和（区間和）を高速に、効率よく求められるデータ構造です。

横一列に、1からNまで、花壇が並んでいて、番号 i （1 <= i <= N）に、いくつかの種を蒔くとします。
このときの範囲 [L, R]（1 <= L <= R <= N）に蒔いた種の合計を求めたいです。

通常なら、R-L+1回の足し算が必要ですが、フェニック木を用いれば、対数時間（O(log N)）で計算が完了します。（ただし、更新も O(log N) になります）

このデータ構造は、ニュージーランドの計算機科学者であるピーター・フェニック（Peter Fenwick）さんの論文により、広く知られるようになりました。
フェニック木という名前も、この方の名前にちなんで付けられています。

今回は、このフェニック木を PHP で実装してみます。

実装

実装したものがこちらです：

<?php
class Fenwick {
    public array $tree;
    public int $size;

    public function __construct(int $n) {
        $this->size = $n;
        $this->tree = array_fill(0, $n, 0);
    }
	// $index は、0-index
    public function add(int $index, int $value): void {
        for ($i=$index; $i<$this->size; $i|=$i + 1) {
            $this->tree[$i] += $value;
        }
    }
	// [0, $a) の区間和。0-index, 0は含む、$aは含まない
	// [$a, $b) は、$this->sum($b) - $this->sum($a);
    public function sum(int $a): int {
		$sum = 0;
        for($i=$a-1; $i>=0; $i=($i & ($i+1))-1) {
            $sum += $this->tree[$i];
        }
        return $sum;
    }
}

// 使い方
$fen = new Fenwick(5);
$fen->add(0, 1);
$fen->add(1, 1);
$fen->add(2, 1);
$fen->add(3, 1);
$fen->add(4, 1);
echo '[1, 1, 1, 1, 1], 0-index'.PHP_EOL;
echo '[0,1)の和: '. $fen->sum(1).PHP_EOL;
echo '[0,2)の和: '. $fen->sum(2).PHP_EOL;
echo '[0,4)の和: '. $fen->sum(4).PHP_EOL;
echo '[0,5)の和: '. $fen->sum(5).PHP_EOL;

基本的な特徴

フェニック木は、特殊な形をした二分木です。
親となるノードの下に、2つの子を持ちます。
それぞれの子も、2つずつ孫を持ち、それが子孫まで続いていきます。

しかし、単純にそれぞれの値をもたせるのではなく、2の累乗区分から、その数字までの和すべてを連動させています。

この感触は、言葉では説明しづらいので、ぜひ「アルゴリズムロジック」というブログの Binary Indexed Tree (BIT) 総まとめ！区間加算や二次元BITまで という記事を参照してください。
図解で解説されているので、イメージしやすいと思います。

上記のブログ記事にもありますが、2の累乗区間に分けた時の、その更新したい数や求めたい範囲を適切に計算するのは、とても面倒そうに感じます。
しかし、 bit 演算（上記の例で言えば、$i|=$i+1や$i=($i & ($i+1)）を適切に用いることで、これを高速に求められます。
ここが、このデータ構造の肝となるところです。

なお、数え方を1から始める（つまり、1-index）方が途中計算の見通しが良いのですが、使い勝手は 0-index のほうが良いので、今回は 0-index で実装しています。
（実装上の難しさは、生成AIのおかげでだいぶ緩和されてきた印象です）

計算量について

たとえば、10万個のデータがあったとしても、 2^16 < 10万 < 2^17 なので、最大でも17回の繰り返し処理で、更新や合算が終わってしまいます。
最悪10万回の繰り返し処理が、たった17回に減るなら、かなりの効果が感じられるでしょう。

「累積和」という考え方をご存知の方は、「累積和を使えば、 O(1)で合算が終わるのでは？」という疑問を持つかもしれません。
確かに、合算の最適化だけであれば、フェニック木よりも累積和の方が、計算効率が高いです。
しかし、累積和は、更新時の計算量が O(N) です。

表にすると、以下のようになります。

つまり、フェニック木は、更新と合算で、同時に高速性が求められる場合に利用すべきデータ構造です。

まとめ

今回は、フェニック木の PHP での実装例を紹介しました。

使いどころによっては、大変強力なデータ構造なので、ぜひ利用してみてください。