別名 BIT(Binary Indexed Tree)
長さ N の配列に対し、
- 要素の
1点変更 - 区間の要素の総和
を O(logN) で求めることが出来るデータ構造です。
fw = FenwickTree.new(arg)引数は、Integer または Array です。
- 引数が
Integerクラスのnのとき、長さnの全ての要素が0で初期化された配列を作ります。 - 引数が長さ
nのArrayクラスの配列aのとき、aで初期化された配列を作ります。
配列の添字は、0-based indexです。
計算量
O(n) (引数がArrayでも同じです)
fw.add(pos, x)a[pos] += xを行います。
posは、0-based indexです。
制約 0 ≦ pos < n
計算量 O(logn)
fw.sum(l, r)a[l] + a[l - 1] + ... + a[r - 1]を返します。
引数は、半開区間です。
実装として、内部で_sum(r) - _sum(l)を返しています。
制約 0 ≦ l ≦ r ≦ n
計算量 O(logn)
fw._sum(pos)a[0] + a[1] + ... + a[pos - 1]を返します。
計算量 O(logn)
- AtCoder ALPC B - Fenwick Tree [ACコード(17074108)]https://atcoder.jp/contests/practice2/submissions/17074108 (1272ms)
- F - Range Xor Query FenwickTree(BIT)をxorに改造するだけでも解けます。 ACコード(821ms)。FenwickTree(BIT)のxor改造版です。
本家ACLライブラリの実装は、内部の配列も0-based indexですが、
本ライブラリは定数倍改善のため、内部の配列への添字が1-based indexです。