【競プロ】無能がフェニック木を１時間で理解してみた abc221_e

【10分】アルゴリズムの理解

部分和の計算と要素の更新を効率よく実行したい時にフェニック木なるものを用いると便利らしい。

特に12枚目のスライドが直感的に分かりやすかった。

【30分】実装してみる・問題を解いてみる

(i & -i)でiの最末尾の1を表せることを自分で考え出せる人天才すぎる。

"""
部分和の計算と要素の更新の効率化に用いる
Binary Indexed Tree
別名 Fenwick Tree(フェニック木)
Segment Treeの機能を制限し、単純化したものと言えそう
BIT[1]=BIT[0+1]=init_list[0]
BIT[2]=BIT[1+1]=init_list[0]+init_list[1]
BIT[3]=BIT[2+1]=init_list[2]
BIT[4]=BIT[3+1]=init_list[0]+・・・+init_list[3]
BIT[5]=BIT[4+1]=init_list[4]
BIT[6]=BIT[5+1]=init_list[4]+init_list[5]
BIT[7]=BIT[6+1]=init_list[6]
BIT[8]=BIT[7+1]=init_list[0]+・・・+init_list[7]
"""

class BIT:

    #segtree:入力のリスト=treeの葉
    #fenwick:入力のリスト=treeの葉 場所によっては同じ
    #葉によって担当する区間の長さが異なる
    def __init__(self,n):
        self.n=n
        self.tree=[0]*(n+1)

    #init_list[i]+=x
    def add(self,i,x):
        #treeは1-indexed, 対象のリストは0-indexed
        i+=1
        while i<=self.n:
            self.tree[i]+=x
            """
            iの最後の1のビットは、そのノードが表現する区間のサイズを表す

            iの負の数を2進数で表すには
            1. すべてのビットを反転させる
            2. 1を加算する
            e.g.) 0110(6)
            1. 1001
            2. 1010(-6)

            これを利用すると
            iの最後の1のビットは(i & -i)で表せる

            更新すべき区間はノード番号に区間の長さを足すと求められる
            e.g.)
            init_list[2]が更新された(tree[3]に対応)
            まずtree[3]を更新
            3の最後の1のビットは1(3&-3によって求まる)
            i+=(3&-3) : i+=1 ->i=4
            次にtree[4]を更新
            4の最後の1のビットは4(4&-4によって求まる)
            i+=(4&-4) : i+=4 -> i=8
            次にtree[8]を更新
            8の最後の1のビットは8
            ・
            ・
            ・
            このような手順を踏むことで,iが区間に含まれるノードを辿れる
            実際,init_list[2]が含まれているノードは3,4,8,・・・
            BIT[3]=BIT[2+1]=init_list[2]
            BIT[4]=BIT[3+1]=init_list[0]+・・・+init_list[3]
            BIT[8]=BIT[7+1]=init_list[0]+・・・+init_list[7]
            """
            i+=(i & -i)

    #init_list[0]+init_list[1]+・・・init_list[i]
    def sum(self,i):
        #treeは1-indexed, 対象のリストは0-indexed
        i+=1
        s=0
        while i>0:
            s+=self.tree[i]
            """
            次に足すべき区間はノード番号から区間の長さを引くことで求まる
            """
            i-=(i & -i)
        return s

    #init_list[l]+・・・+init_list[r-1]
    def sumlr(self,l,r):
        return self.sum(r-1)-self.sum(l-1)

n,q=map(int,input().split())
a=list(map(int,input().split()))
bit=BIT(n)
for i in range(n):
    bit.add(i,a[i])
for _ in range(q):
    b,c,d=map(int,input().split())
    if(b==0):
        bit.add(c,d)
    else:
        print(bit.sumlr(c,d))