Fenwick Treeの追加

[noss3885]

いわゆる Binary Indexed Tree。長さ n の配列 a に対して

• a[i] に x を加算
• 区間和 a[l]+...a[r-1] を求める

をそれぞれ O(log N) で行うデータ構造。

参考資料

• AtCoder Liblary (CC0)

テスト問題

• https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
• https://judge.yosupo.jp/problem/point_add_range_sum

[rogi52]

書きます。