「フェニック木」の版間の差分
削除された内容 追加された内容
ページ「Fenwick tree」の翻訳により作成 |
翻訳ツールでできなかった表記の訂正 |
||
2行目:
'''フェニック木''' または '''Binary Indexed Tree (BIT)''' とは、部分和の計算と要素の更新の両方を効率的に行える[[木構造]]である。1994年に[[算術符号|算術符号化]]を用いた[[データ圧縮|圧縮アルゴリズム]]の計算を効率化するためにピーター・フェニックにより提案された木構造である<ref>{{Cite journal|last=Peter M. Fenwick|author=Peter M. Fenwick|year=1994|title=A new data structure for cumulative frequency tables|url=http://camlunity.ru/swap/Library/Computer%20Science/Algorithms%20and%20Data%20Structures/fenwick-tree.pdf|journal=Software: Practice and Experience|volume=24|issue=3|pages=327–336|DOI=10.1002/spe.4380240306}}</ref>。
単なる[[数列]]として保存する場合と比較して、フェニック木は要素の更新と部分和の計算の両方をバランスよく行える。数列としてデータを保存する場合、 ''n'' 要素の数列には、要素そのものか、区間和を格納する手法が考えられる。要素そのものを格納した場合には、区間和を計算するために区間の長さに比例した時間がかかり、区間和を格納した場合には要素の更新に数列の長さに比例した時間がかかる（要素そのものを格納した場合には要素の更新は定数時間で可能であり、区間和を格納すれば区間和の計算は定数時間で可能である）。フェニック木は要素の更新と区間和の計算の両方を <math>O(\log n )</math> で可能とする構造である。具体的には、木構造のそれぞれのノードが持つ値を、そのノードの部分木の要素の和とすることで実現している。
== 目的 ==
9行目:
フェニック木は算術符号のアルゴリズムの効率化のために開発されたと言える。算術符号の符号化には文字の出現頻度（出現回数）の計算と、その文字までの累積確率が必要である。そのため、区間和を効率的に計算可能なデータ構造の開発が必要であった。
フェニック木を使うことで、部分和を <math>O(\log n )</math> 回の演算で計算することを可能とした。また、最初の要素からの和である''部分和 ''だけでなく、任意の区間の和である ''区間和'' も同様に
フェニック木を拡張することで多次元配列の部分配列にも対応することが可能である。このデータ構造においては、それぞれの操作を <math>O(4^{d}\log_{d} n )</math> 時間で行える。ただし、''d ''は次元数であり、''n'' はそれぞれの次元の要素数である<ref>{{Cite journal|last=Pushkar Mishra|author=Pushkar Mishra|year=2013|title=A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays|arxiv=1311.6093|DOI=10.13140/RG.2.1.2394.2485}}</ref>。
== 説明 ==
フェニック木は木構造を元に作られたが、実際には[[二分ヒープ]]の実装のような、1次元配列を用いた暗黙のデータ構造として実装される。あるノードを表すインデックスが与えられた場合、その親と子のインデックスは、そのインデックスに[[ビット演算]]を施すことで計算可能である。例えば、親のインデックスは最下位の"1"であるビットを0にしたインデックスである（1010に対しては1000）。配列の各要素には部分木の要素の和が格納されており、その部分木の合計を足し合わせることで、部分和（もしくは任意の求めたい区間和）を計算できる。データの値を更新する場合には、変更された値を含むノード容易に特定でき、後述するように順に遡りながら更新可能である。
フェニック木を作るにあたって必要な前処理は、 <math
フェニック木は"1"であるビットを基準にで考えるとわかりやすい。 インデックス ''i ''が2の累乗である要素は、''i'' 要素までの和を持つ。インデックス ''i'' が2つの異なる2の累乗の和（例えば12 = 8+4）である要素は、その2つの要素の間の区間和を持つ。一般に各要素はその親以降の値の合計を持つ（親ノードのインデックスは、最下位の"1"であるビットを0にすることで得られる） 。
22行目:
所望の部分和を計算するためには、インデックスの2進表記を用い、2進表記で1であるビットに対応する要素を足し合わせれば良い。
例えば、最初の11要素の和を求めたい場合には、まず11を2進法で表記して 1011<sub>2</sub> を得る。 この表記には3つの1が含まれているため、1000<sub>2</sub>、1010<sub>2</sub> 、1011<sub>2</sub>の3つを足し合わせれば良い。 これらはそれぞれ、 1 - 8、9 - 10、11の和に対応している。"1"であるビットの数は配列のサイズのビット数で抑えられるため、<math>O(
次に、11番目の要素を更新する場合を考える。更新が必要な要素は、1011<sub>2</sub>、1100<sub>2</sub>、10000<sub>2</sub>の3要素である。これの位置は、最下位の"1"であるビットから繰り上げることによって得られる。これらはそれぞれ、11、9 - 12、1 - 16の和に対応する。この場合、値の更新は配列のサイズのビット数で抑えられるため、<math>O(
== 実装例 ==
C言語による単純な実装を紹介する。単なる数列に比べ、前処理は20%ほど長くなる。しかし、この実装のように非常に大きな数列を用いる場合にはその後の操作（要素の更新と部分和の計算）が約1600倍の速度で可能となる。
下の実装では他の手法との比較を含む。
<source lang="C">
/*******************************************************************/
/* 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;
}
</source>
== 参照 ==
* [[級数]]
== 参考文献 ==
41 ⟶ 211行目:
* [http://michaelnielsen.org/polymath1/index.php?title=Updating_partial_sums_with_Fenwick_tree An entry on Fenwick Trees on Polymath wiki]
* [http://cs.stackexchange.com/questions/10538/]
{{DEFAULTSORT:ふえにつくき}}
{{木構造 (データ構造)}}
[[Category:データ構造]]
| |||