長さ $N$ の long型配列に対し,

• 要素の1点変更
• 区間の要素の総和

を $O(\log N)$ の時間で求めることができるデータ構造です.

public FenwickTree(int n)

長さ $n$ の配列 $a_0, a_1, \dots, a_{n-1}$を作ります. 初期値はすべて0です. 計算量: $O(n)$

public void add(int p, long x)

配列の第$p$要素に$x$を加える. すなわち, a[p] += x のこと. 計算量: $O(\log N)$

public long sum(int l, int r)

$a_l + a_{l+1} + \dots + a_{r-1}$の値を返す. 計算量: $O(\log n)$

[[https://atcoder.jp/contests/practice2/submissions/16573339]]