フェニック木
級数
フェニック木は木構造を元に作られたが、実際には二分ヒープの実装のような、1次元配列を用いた暗黙のデータ構造として実装される。あるノードを表すインデックスが与えられた場合、その親と子のインデックスは、そのインデックスにビット演算を施すことで計算可能である。例えば、親のインデックスは最下位の"1"であるビットを0にしたインデックスである(1010に対しては1000)。配列の各要素には部分木の要素の和が格納されており、その部分木の合計を足し合わせることで、部分和(もしくは任意の求めたい区間和)を計算できる。データの値を更新する場合には、変更された値を含むノード容易に特定でき、後述するように順に遡りながら更新可能である。
フェニック木を作るにあたって必要な前処理は、 O ( n ) {\displaystyle O(n)} 時間で終了する。部分和の計算以外にも、すべての値が正の場合には値のインデックスの検索が、すべての値が負でない場合にはすべてのインデックスの値の指定も効率的である。また、 O ( n ) {\displaystyle O(n)} 時間で全ての係数を定数倍することが可能である。
フェニック木は"1"であるビットを基準にで考えるとわかりやすい。 インデックス i が2の累乗である要素は、i 要素までの和を持つ。