pythonで双対セグ木を書いてみた

競プロやってます。atcoder緑です。双対セグ木のコードを載せます。

区間更新・一点取得が可能なデータ構造があると便利な　この問題　において区間取得できる遅延セグ木だとTLEしたのでパクリ自作しました。(一応上の問題のコードも置いときます)

~
def segfunc(x,y):
    return x+y
#self.lazyは1~indexed
#self.add(l,r,x)は0~indexdの開区間[l,r)
#self.get(i)は0~indexd
class cheapSegTree:
    def __init__(self,n,segfunc):
        self.segfunc=segfunc
        self.num = 1<<(n-1).bit_length()
        self.lazy = [0]*2*self.num
    
    def update(self,l,r,x):
        #下のコードで self.lazy[index]が[l,r)に含まれるindexを網羅できるらしい
        #ノーマルセグ木の区間取得とかでもつかえてすごいけど原理は分からない
        l+=self.num
        r+=self.num
        while l<r:
            if l&1:
                self.lazy[l]=self.segfunc(self.lazy[l],x)
                l+=1
            if r&1:
                self.lazy[r-1]=self.segfunc(self.lazy[r-1],x)
            l>>=1
            r>>=1

    def get(self,i):
        res=0
        i+=self.num
        while i:
            res=self.segfunc(res,self.lazy[i])
            i>>=1
        return res
~

僕の理解(というか予想)では双対セグ木・遅延セグ木においては値を取得するときに蓄積していた更新値を反映した後取得した範囲の更新値を初期化すると思うのですが、上記の問題においては一度取得した範囲は二度と参照しなくてよいので実装を省略しています。というか初期化の仕方はわかりません。
※追記　双対は初期化の必要ないんじゃね？ってなったのでこのコードはれっきとした双対セグ木です。多分

紹介するコードはネットにあった遅延セグ木のコードをいじったものです。元ネタのurlはこちら ←とても参考になります。

緑コーダーが書いたコード・文章なので間違いを含む可能性がとてもあります。