Binary Indexed Tree
中間のノードが子ノード（の持つ値）の和を計算するツリー構造を、Binary Indexed Treeというと『プログラミングコンテストチャレンジブック』から知った。バイナリエディタでも同様の構造を使っているが、赤黒木を使って深さを平衡に保つことで*1、巨大なドキュメントに対する編集を高速に実行できるようPiece Tableを実装していたりする（つづ・・かない）。
*1:Qtのqfragmentmapという実装ですが
中間のノードが子ノード（の持つ値）の和を計算するツリー構造を、Binary Indexed Treeというと『プログラミングコンテストチャレンジブック』から知った。バイナリエディタでも同様の構造を使っているが、赤黒木を使って深さを平衡に保つことで*1、巨大なドキュメントに対する編集を高速に実行できるようPiece Tableを実装していたりする（つづ・・かない）。
*1:Qtのqfragmentmapという実装ですが