LoginSignup
26
13

More than 3 years have passed since last update.

@ether2420(ether 2420)

【Python】セグ木、遅延セグ木【AtCoder】

Last updated at Posted at 2021-02-02

ABC190
F - Shift and Inversions
ででてきたセグ木をこれを機会に、
自分用のライブラリ(Python)を作成してみた。
(BITもセグ木の親戚らしい。
上の問題は、BIT構造でも解けますが、セグ木でも解けます。)

実装方法で色々ググったけど、
自分にピンとくる記事がなかなか見つからなかったので記事にしてみる。

そもそもセグ木って何者！？

セグ木初心者は、まずかつっぱさんのYoutubeをみましょう！
めちゃくちゃ わかりやすい！！！
【木マスター養成講座】4-1. Segment木ってなに〜？導入編【競プロかつっぱ】
【木マスター養成講座】4-2. Segment木ってなに〜？なんかうまく区間取ってくる編【競プロかつっぱ】
【木マスター養成講座】4-3. Segment木ってなに〜？RAQ編【競プロかつっぱ】

上記3動画を見ることでセグ木の基本が雰囲気理解できるようになります！

セグ木基本問題4問！！！

DSL_2_A - Range Minimum Query
DSL_2_B - Range Sum Query
DSL_2_E - Range Add Query (RAQ)
DSL_2_F - RMQ and RUQ

  • 上2つは1箇所だけ更新 → ①普通のセグ木

  • 下2つは区間更新 → 遅延セグ木(②区間加算用、③区間更新用)

を使います！
このセグ木と遅延セグ木でぴよぴよ級どころかつよつよ級までたぶんいけます。
（つよつよ級までいけなかったらごめんなさい！）

以下、それぞれ自作ライブラリを貼っていきます。
①普通のセグ木
②遅延セグ木(区間加算用）
③遅延セグ木(区間更新用)
使い方にちょっとした慣れが必要だと思うので、上の4問に是非チャレンジしてみてください！

※一応上記4問、自作ライブラリでAC確認済ですが、万が一バグがあれば教えてください！

使用例と引数(segfuncと単位元)についての簡単なまとめ

※このリンクの記事の説明がわかりやすいです！！！

#使用例
st = SegTree([0]*N,segfunc,0)
st.query(0,4)
"""
操作 segfunc 単位元
最小値 min(x,y) math.inf
最大値 max(x,y) -math.inf
区間和 x+y 0
区間積 x*y 1
最大公約数 math.gcd(x,y) 0
"""

①普通のセグ木

query(l,r)では、rは+1の値を入れてあげましょう！
例えば、0から3までの区間の答えがほしければ、
query(0,4)です！

test.py
def segfunc(x,y):
    return x+y
class SegTree:
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1<<(n-1).bit_length()
        self.tree = [ide_ele]*2*self.num
        for i in range(n):
            self.tree[self.num+i] = init_val[i]
        for i in range(self.num-1,0,-1):
            self.tree[i] = self.segfunc(self.tree[2*i],self.tree[2*i+1])
    def add(self,k,x):
        k += self.num
        self.tree[k] += x
        while k>1:
            self.tree[k>>1] = self.segfunc(self.tree[k],self.tree[k^1])
            k >>= 1
    def update(self,k,x):
        k += self.num
        self.tree[k] = x
        while k>1:
            self.tree[k>>1] = self.segfunc(self.tree[k],self.tree[k^1])
            k >>= 1
    def query(self,l,r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                res = self.segfunc(res,self.tree[l])
                l += 1
            if r&1:
                res = self.segfunc(res,self.tree[r-1])
            l >>= 1
            r >>= 1
        return res

②遅延セグ木(区間加算用）

test.py
def segfunc(x,y):
    return x+y
class LazySegTree_RAQ:
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1<<(n-1).bit_length()
        self.tree = [ide_ele]*2*self.num
        self.lazy = [0]*2*self.num
        for i in range(n):
            self.tree[self.num+i] = init_val[i]
        for i in range(self.num-1,0,-1):
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
    def gindex(self,l,r):
        l += self.num
        r += self.num
        lm = l>>(l&-l).bit_length()
        rm = r>>(r&-r).bit_length()
        while r>l:
            if l<=lm:
                yield l
            if r<=rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v==0:
                continue
            self.lazy[i] = 0
            self.lazy[2*i] += v
            self.lazy[2*i+1] += v
            self.tree[2*i] += v
            self.tree[2*i+1] += v
    def add(self,l,r,x):
        ids = self.gindex(l,r)
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                self.lazy[l] += x
                self.tree[l] += x
                l += 1
            if r&1:
                self.lazy[r-1] += x
                self.tree[r-1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1]) + self.lazy[i]
    def query(self,l,r):
        self.propagates(*self.gindex(l,r))
        res = self.ide_ele
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                res = self.segfunc(res,self.tree[l])
                l += 1
            if r&1:
                res = self.segfunc(res,self.tree[r-1])
            l >>= 1
            r >>= 1
        return res

③遅延セグ木(区間更新用)

self.lazyの箇所
②遅延セグ木(区間加算用）みたいに0を使うとうまくいかない。
Noneを使う！
他にも違うところがちらほらあったりする。

test.py
def segfunc(x,y):
    return min(x,y)
class LazySegTree_RUQ:
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1<<(n-1).bit_length()
        self.tree = [ide_ele]*2*self.num
        self.lazy = [None]*2*self.num
        for i in range(n):
            self.tree[self.num+i] = init_val[i]
        for i in range(self.num-1,0,-1):
            self.tree[i] = self.segfunc(self.tree[2*i],self.tree[2*i+1])
    def gindex(self,l,r):
        l += self.num
        r += self.num
        lm = l>>(l&-l).bit_length()
        rm = r>>(r&-r).bit_length()
        while r>l:
            if l<=lm:
                yield l
            if r<=rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[i] = None
            self.lazy[2*i] = v
            self.lazy[2*i+1] = v
            self.tree[2*i] = v
            self.tree[2*i+1] = v
    def update(self,l,r,x):
        ids = self.gindex(l,r)
        self.propagates(*self.gindex(l,r))
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                self.lazy[l] = x
                self.tree[l] = x
                l += 1
            if r&1:
                self.lazy[r-1] = x
                self.tree[r-1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
    def query(self,l,r):
        ids = self.gindex(l,r)
        self.propagates(*self.gindex(l,r))
        res = self.ide_ele
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                res = self.segfunc(res,self.tree[l])
                l += 1
            if r&1:
                res = self.segfunc(res,self.tree[r-1])
            l >>= 1
            r >>= 1
        return res

実装の参考になった記事

いろいろググりましたが、個人的に一番わかりやすかった記事！
Pythonで遅延セグ木(デバッグのお願い)
@takayg1 さんありがとうございました！！

（追記）
後からみつけたけど、@takayg1 さんのこの記事もオススメです！
Pythonでアルゴリズム（セグメント木）（実践）

おわり！

26
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
26
13