フェニック木
インデックス i が2つの異なる2の累乗の和(例えば12 = 8+4)である要素は、その2つの要素の間の区間和を持つ。一般に各要素はその親以降の値の合計を持つ(親ノードのインデックスは、最下位の"1"であるビットを0にすることで得られる) 。
所望の部分和を計算するためには、インデックスの2進表記を用い、2進表記で1であるビットに対応する要素を足し合わせれば良い。
例えば、最初の11要素の和を求めたい場合には、まず11を2進法で表記して 10112 を得る。 この表記には3つの1が含まれているため、10002、10102 、10112の3つを足し合わせれば良い。 これらはそれぞれ、 1 - 8、9 - 10、11の和に対応している。"1"であるビットの数は配列のサイズのビット数で抑えられるため、 O ( log  n ) {\displaystyle O(\log n)} で区間和を計算可能である。
次に、11番目の要素を更新する場合を考える。更新が必要な要素は、10112、11002、100002の3要素である。これの位置は、最下位の"1"であるビットから繰り上げることによって得られる。これらはそれぞれ、11、9 - 12、1 - 16の和に対応する。この場合、値の更新は配列のサイズのビット数で抑えられるため、 O ( log  n ) {\displaystyle O(\log n)} で更新可能である。