【Pythonで実装】フェニック木（Binary Indexed Tree）が美しすぎて感動した話（部分和の計算と更新） - Qiita

はじめに 最近競プロ熱が再燃して精進している、いおと言います。 AtCoder緑色で、まだまだデータ構造やアルゴリズムを勉強中の身です。 典型90問で出会った「フェニック木」というデータ構造が美しすぎて感動したため、記事にすることにしました。 この美しさが少しでも伝わればと思います。 フェニック木とは フェニック木 または Binary Indexed Tree (BIT) とは、部分和の計算と要素の更新の両方を効率的に行える木構造である。1994年に算術符号化を用いた圧縮アルゴリズムの計算を効率化するためにピーター・フェニックにより提案された木構造である (WikiPediaより引用） 簡単にいうと、ある配列に対して部分和を効率的に求められる（計算量でいうとO(log n)）上に、値の更新も効率的に行える木構造になります。 サイズNの配列で実現できる上に、実装がとっても簡単なのが魅力的！