フェニック木

配列[1, 2, 3, 4, 5]を順次挿入し、フェニック木を構築する様子

フェニック木 または Binary Indexed Tree (BIT) とは、部分和の計算と要素の更新の両方を効率的に行える木構造である。1994年に算術符号化を用いた圧縮アルゴリズムの計算を効率化するためにピーター・フェニックにより提案された木構造である^[1]。

単なる数列として保存する場合と比較して、フェニック木は要素の更新と部分和の計算の両方をバランスよく行える。数列としてデータを保存する場合、 n 要素の数列には、要素そのものか、区間和を格納する手法が考えられる。要素そのものを格納した場合には、区間和を計算するために区間の長さに比例した時間がかかり、区間和を格納した場合には要素の更新に数列の長さに比例した時間がかかる（要素そのものを格納した場合には要素の更新は定数時間で可能であり、区間和を格納すれば区間和の計算は定数時間で可能である）。フェニック木は要素の更新と区間和の計算の両方を ${\displaystyle O(\log n)}$ で可能とする構造である。具体的には、木構造のそれぞれのノードが持つ値を、そのノードの部分木の要素の和とすることで実現している。

目的

上で述べた算術符号のように、数列の各インデックスまでの部分和が必要となる場合がある。任意のインデックス間の区間和を効率的に計算できるだけでなく、データ内の要素の更新とその更新による変化を効率的に反映可能なデータ構造を実現するために、フェニック木が開発された。

フェニック木は算術符号のアルゴリズムの効率化のために開発されたと言える。算術符号の符号化には文字の出現頻度（出現回数）の計算と、その文字までの累積確率が必要である。そのため、区間和を効率的に計算可能なデータ構造の開発が必要であった。

フェニック木を使うことで、部分和を ${\displaystyle O(\log n)}$ 回の演算で計算することを可能とした。また、最初の要素からの和である部分和 だけでなく、任意の区間の和である 区間和 も同様に ${\displaystyle O(\log n)}$ で計算可能とした。

フェニック木を拡張することで多次元配列の部分配列にも対応することが可能である。このデータ構造においては、それぞれの操作を ${\displaystyle O(4^{d}\log _{d}n)}$ 時間で行える。ただし、d は次元数であり、n はそれぞれの次元の要素数である^[2]。

説明

フェニック木は木構造を元に作られたが、実際には二分ヒープの実装のような、1次元配列を用いた暗黙のデータ構造として実装される。あるノードを表すインデックスが与えられた場合、その親と子のインデックスは、そのインデックスにビット演算を施すことで計算可能である。例えば、親のインデックスは最下位の"1"であるビットを0にしたインデックスである（1010に対しては1000）。配列の各要素には部分木の要素の和が格納されており、その部分木の合計を足し合わせることで、部分和（もしくは任意の求めたい区間和）を計算できる。データの値を更新する場合には、変更された値を含むノード容易に特定でき、後述するように順に遡りながら更新可能である。

フェニック木を作るにあたって必要な前処理は、 ${\displaystyle O(n)}$ 時間で終了する。部分和の計算以外にも、すべての値が正の場合には値のインデックスの検索が、すべての値が負でない場合にはすべてのインデックスの値の指定も効率的である。また、 ${\displaystyle O(n)}$ 時間で全ての係数を定数倍することが可能である。

フェニック木は"1"であるビットを基準にで考えるとわかりやすい。 インデックス i が2の累乗である要素は、i 要素までの和を持つ。インデックス i が2つの異なる2の累乗の和（例えば12 = 8+4）である要素は、その2つの要素の間の区間和を持つ。一般に各要素はその親以降の値の合計を持つ（親ノードのインデックスは、最下位の"1"であるビットを0にすることで得られる） 。

所望の部分和を計算するためには、インデックスの2進表記を用い、2進表記で1であるビットに対応する要素を足し合わせれば良い。

例えば、最初の11要素の和を求めたい場合には、まず11を2進法で表記して 1011₂ を得る。 この表記には3つの1が含まれているため、1000₂、1010₂ 、1011₂の3つを足し合わせれば良い。 これらはそれぞれ、 1 - 8、9 - 10、11の和に対応している。"1"であるビットの数は配列のサイズのビット数で抑えられるため、${\displaystyle O(\log n)}$ で区間和を計算可能である。

次に、11番目の要素を更新する場合を考える。更新が必要な要素は、1011₂、1100₂、10000₂の3要素である。これの位置は、最下位の"1"であるビットから繰り上げることによって得られる。これらはそれぞれ、11、9 - 12、1 - 16の和に対応する。この場合、値の更新は配列のサイズのビット数で抑えられるため、${\displaystyle O(\log n)}$ で更新可能である。

実装例

C言語による単純な実装を紹介する。単なる数列に比べ、前処理は20%ほど長くなる。しかし、この実装のように非常に大きな数列を用いる場合にはその後の操作（要素の更新と部分和の計算）が約1600倍の速度で可能となる。 下の実装では他の手法との比較を含む。

/*******************************************************************/
/* This program demonstrates the speedup for a Fenwick tree vs a        */
/* flat array for performing multiple prefix sums.  It generates a             */
/* sequence of random numbers, then performs 1000 summations,      */
/* each of which starts and ends at random indices.                                  */
/*******************************************************************/
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// Number of elements in the array
#define N (4*1024*1024)		// Elements in the array
#define COUNTS 1024		// Size of values stored
typedef unsigned long sum_t;	// Should be able to hold N * (COUNTS - 1)

// Number of queries to perform
#define NQUERIES 1000

// Isolate the least significant 1 bit.  E.g. LSB(0x1234) == 4.
#define LSB(i) ((i) & -(i))

// Fen_sum: return the sum of the first i elements, 0 through i-1.
sum_t Fen_sum(sum_t const *a, unsigned int i) 
{
	sum_t sum = 0;
	while (i) {
		sum += a[i-1];
		i -= LSB(i);
	}
	return sum;
}

// Fen_add: add k to element i (and thus Fen_sum(a, j) for all j > i)
void Fen_add(sum_t *a, unsigned int size, sum_t delta, unsigned int i) 
{
	while (i < size) {
		a[i] += delta;
		i += LSB(i+1);
	}
}

// Fen_range: Returns the sum of the elements [i..j-1]
// This could be written as "Fen_sum(a, j) - Fen_sum(a, i)",
// but it is possible to do it in less time (particularly for
// small ranges) by avoiding the terms that the two sums have
// in common.
sum_t Fen_range(sum_t const *a, unsigned int i, unsigned int j)
{
	sum_t sum = 0;

	while (j > i) {
		sum += a[j-1];
		j -= LSB(j);
	}

	while (i > j) {
		sum -= a[i-1];
		i -= LSB(i);
	}
	return sum;
}

// Fen_get: Returns the value of the element at index i
// (The time is proportional to the number of trailing 1 bits
// in i.  So even numbers are fast, and i = 0xffff takes 16 steps.)
sum_t Fen_get(sum_t const *a, unsigned int i)
{
	return Fen_range(a, i, i+1);
}

// Fen_set: sets the value of the element at index i
void Fen_set(sum_t *a, unsigned int size, sum_t value, unsigned int i)
{
	Fen_add(a, size, value - Fen_get(a, i), i);
}

// It's possible to initialize a Fenwick tree using Fen_add or
// Fen_set (you can even do the latter in-place if you go backward
// through the array), but for bulk initialization, this is faster.
void Fen_init(sum_t *a, unsigned int size)
{
	for (unsigned int i = 0; i < size; i++) {
		unsigned int j = i + LSB(i+1);
		if (j < size)
			a[j] += a[i];
	}
}

// main: allocates an array of numbers and fills it with a sequence of
// random numbers, then performs a series of summations (queries).  It
// then repeats the process using a Fenwick tree rather than a flat
// array.  The sequence of random numbers and the bounds of each query
// are identical for the flat array and the Fenwick tree.  The time
// required to populate the data structure and the total time required
// for all queries is calculated and reported for the flat array and
// for the Fenwick tree.

int main(void)
{
	sum_t *a;
	unsigned int queries[NQUERIES*2];
	clock_t time1, time2, time3;
	time_t seed = time(NULL);

	// generate the bounds for all of the queries
	srandom(seed + 1);
	for (unsigned int i = 0; i < NQUERIES * 2; i += 2) {
		unsigned int q = random() % N, r = random() % N;
		bool reverse = q > r;

		queries[i +  reverse] = q;
		queries[i + !reverse] = r;
	}

	// allocate the array of sums
	a = malloc(N * sizeof *a);

	// The following loop forces all pages into memory (otherwise the
	// timing of the algorithm could include a lot of page faults)
	for (unsigned int i = 0; i < N; i++)
		a[i] = 0;

	/*****************************************************************/
	/*   FLAT ARRAY METHOD                                           */
	/*****************************************************************/

	time1 = clock();
	// Store random numbers in a flat array
	srandom(seed);
	for (unsigned int i = 0; i < N; i++)
		a[i] = random() % COUNTS;
	time2 = clock();	// time2 - time1 = time for setup
	// perform the queries
	for (unsigned int j = 0; j < NQUERIES * 2; j += 2) {
		sum_t asum = 0;
		for (unsigned int i = queries[j]; i < queries[j+1]; i++)
			asum += a[i];
		printf(" %lu", asum);
	}
	time3 = clock();	// time3 - time2 = time for queries

	printf("\nFlat Array:\n Build: %f\n Query: %f\n",
		(time2-time1)*(1.0/CLOCKS_PER_SEC),
		(time3-time2)*(1.0/CLOCKS_PER_SEC));

	/*****************************************************************/
	/*   FENWICK TREE METHOD                                         */
	/*****************************************************************/

	time1 = clock();
	// Store the same random numbers in a Fenwick tree
	srandom(seed);
	for (unsigned int i = 0; i < N; i++)
		a[i] = random() % COUNTS;
	Fen_init(a, N);
	time2 = clock();	// time2 - time1 = time for setup
	// perform the queries
	for (unsigned int j = 0; j < NQUERIES * 2; j += 2)
		printf(" %lu", Fen_range(a, queries[j], queries[j+1]));
	time3 = clock();	// time3 - time2 = time for queries

	printf("\nFenwick:\n Build: %f\n Query: %f\n",
		(time2-time1)*(1.0/CLOCKS_PER_SEC),
		(time3-time2)*(1.0/CLOCKS_PER_SEC));

	free(a);
	return 0;
}

参照

• 級数

参考文献

1. Peter M. Fenwick (1994). “A new data structure for cumulative frequency tables”. Software: Practice and Experience 24 (3): 327–336. doi:10.1002/spe.4380240306. http://camlunity.ru/swap/Library/Computer%20Science/Algorithms%20and%20Data%20Structures/fenwick-tree.pdf. 
2. Pushkar Mishra (2013). A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays. arXiv:1311.6093. doi:10.13140/RG.2.1.2394.2485. 

外部リンク

• A tutorial on Fenwick Trees on TopCoder
• An article on Fenwick Trees on Algorithmist
• An entry on Fenwick Trees on Polymath wiki
• [1]