「フェニック木」の版間の差分
削除された内容 追加された内容
翻訳ツールでできなかった表記の訂正 |
m →top: 曖昧さ回避 |
||
1行目:
[[ファイル:BITDemo.gif|サムネイル|200x200ピクセル|配列[1, 2, 3, 4, 5]を順次挿入し、フェニック木を構築する様子]]
'''フェニック木''' または '''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> で可能とする構造である。具体的には、木構造のそれぞれのノードが持つ値を、そのノードの部分木の要素の和とすることで実現している。
| |||