About: フェニック木

フェニック木 または Binary Indexed Tree (BIT) とは、部分和の計算と要素の更新の両方を効率的に行える木構造である。1994年に算術符号化を用いた圧縮アルゴリズムの計算を効率化するためにピーター・フェニックにより提案された木構造である。 単なる数列として保存する場合と比較して、フェニック木は要素の更新と部分和の計算の両方をバランスよく行える。数列としてデータを保存する場合、 n 要素の数列には、要素そのものか、区間和を格納する手法が考えられる。要素そのものを格納した場合には、区間和を計算するために区間の長さに比例した時間がかかり、区間和を格納した場合には要素の更新に数列の長さに比例した時間がかかる（要素そのものを格納した場合には要素の更新は定数時間で可能であり、区間和を格納すれば区間和の計算は定数時間で可能である）。フェニック木は要素の更新と区間和の計算の両方を で可能とする構造である。具体的には、木構造のそれぞれのノードが持つ値を、そのノードの部分木の要素の和とすることで実現している。