Fenwick Tree

長さ $N$ の配列に対し、

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

を $O(\log N)$ で求めることが出来るデータ構造です。

コンストラクタ

var fw = initFenwickTree[T](n:int):fenwick_tree[T]
var fw = FenwickTreeType(T).init(n)
var fw = FenwickTree.getType(T).init(n)

• 長さ $n$ の配列 $a_0, a_1, \cdots, a_{n-1}$ を作ります。初期値はすべて $0$ です。

制約

• $T$ は int / uint / ll / ull / modint
• $0 \leq n \leq 10^8$

計算量

• $O(n)$

add

fw.add(p:int, x:T):void

a[p] += x を行う

制約

• $0 \leq p < n$

計算量

• $O(\log n)$

sum

fw.sum(l..<r):T
fw[l..<r]:T

a[l] + a[l + 1] + ... + a[r - 1] を返す。 T が整数型(int / uint / ll / ull)の場合、答えがオーバーフローしたならば $\bmod 2^{\mathrm{bit}}$ で等しい値が返る。 Nimに特有の機能として[]演算子でも呼べる他、BackwardsIndexでのアクセスも可能です。例えば、fw[3..^1]でインデックス3以降の全ての和が返されます。

制約

• $0 \leq l \leq r \leq n$

計算量

• $O(\log n)$

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_b