データ構造 Fenwick tree (binary indexed tree, BIT) にどっぷりと入門し、その美しき構造に心を洗われたい方のための紹介記事です!アルゴリズム競技プログラミングデータ構造FenwickTreeBinaryIndexTree $$ \newcommand \lsb { \mathrm { lsb } } $$ Fenwick tree (Binary indexed tree, BIT) をお勉強しましたところ、大変美しい構造を持つことがわかりましたから、共有させていただきたいと思います。案外長くなってしまって、自分でもびっくりしています。 第一章:Fenwick tree の基本機能 初めての方はまずこちらです。 問題 整数の配列 $a$ があります。これに次のようなクエリが飛んできます。 操作 内容