fenwicktree

fenwick tree

数列(a_i)(i=0,...,n-1)に対して以下のクエリを高速に行えます。

• a_iをxに更新する
• kに対して、a_0+...+a_{k-1}を求める

初期化

FT=fenwick_tree(N)

Nは配列のサイズです。 初期化した時、最初の配列のサイズは全て0になっています。 【注意】もしバグったら、まずは初期値を間違えてないか確認しましょう。

更新

FT.add(i,a)

i番目の値をaに更新します

和を求める1

print(FT.sum0(r))

a_0+...+a_{r-1}の総和、つまりsum(a[:r])を求めます。

和を求める2

print(FT.sum(l,r))

a_l+...+a_{r-1}の総和、つまりsum(a[l:r])を求めます。

使用例

使用例1

(https://atcoder.jp/contests/practice2/tasks/practice2_b)

class fenwick_tree():
    #(中略)
 
N,Q=map(int,input().split())
a=[int(i) for i in input().split()]
FT=fenwick_tree(N)
for i in range(N):
    FT.add(i,a[i])
#ここまで初期化
#ここからクエリに答える
for i in range(Q):
    t,a,b=map(int,input().split())
    if t==0:
        FT.add(a,b)
    else:
        print(FT.sum(a,b))