Fenwick Tree
長さ
$ N
のある数列
$ A
に対して以下の操作をそれぞれ
$ O(log \, N)
で実行できるデータ構造。ただし、
$ A_i
は左から
$ i
番目の値のことを表す。
操作1.
$ i, x
を指定して、
$ A_i
に値
$ x
を足す。
操作2.
$ l,r
を指定して、
$ A_l, A_{l+1},...,A_r
の合計値を知る。
参考
【Fenwick_Tree編】AtCoder Library 解読 〜Pythonでの実装まで〜