フェニック木
上で述べた算術符号のように、数列の各インデックスまでの部分和が必要となる場合がある。任意のインデックス間の区間和を効率的に計算できるだけでなく、データ内の要素の更新とその更新による変化を効率的に反映可能なデータ構造を実現するために、フェニック木が開発された。
フェニック木は算術符号のアルゴリズムの効率化のために開発されたと言える。算術符号の符号化には文字の出現頻度(出現回数)の計算と、その文字までの累積確率が必要である。そのため、区間和を効率的に計算可能なデータ構造の開発が必要であった。
フェニック木を使うことで、部分和を O ( log  n ) {\displaystyle O(\log n)} 回の演算で計算することを可能とした。また、最初の要素からの和である部分和 だけでなく、任意の区間の和である 区間和 も同様に O ( log  n ) {\displaystyle O(\log n)} で計算可能とした。
フェニック木を拡張することで多次元配列の部分配列にも対応することが可能である。このデータ構造においては、それぞれの操作を O ( 4 d log d  n ) {\displaystyle O(4^{d}\log _{d}n)} 時間で行える。ただし、d は次元数であり、n はそれぞれの次元の要素数である。