LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@flour(kinako desu)

LazySegmentTreeチートシート【AtCoder・Python】

Posted at

AtCoder Library

2023年8月にAtCoderにACL(AtCoder Library)というものが追加され、dsu(UnionFindTree)や、floor_sumなどいろいろなアルゴリズムが実装されたライブラリをインポートできるようになりました。
Pythonにおいても以下のリポジトリによる実装が使用できるようになっています。
https://github.com/not522/ac-library-python

今回はその中でLazySegmentTreeについて、コンテスト中に使えるサンプルを残しておきます

区間加算・区間最大値取得

from atcoder.lazysegtree import LazySegTree

INF = float('INF')

# 値の2項演算
def op(value1, value2):
    return max(value1, value2)

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return f + value

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return f + g

# 値の単位元
e = -INF

# 作用素の単位元
id_ = 0

l = [0,1,2,3,4,5,6]
LST = LazySegTree(op, e, mapping, composition, id_, l)
使用例 
# [2,5)に1加算
LST.apply(2,5,1) # [0,1,3,4,5,5,6]

# 区間の演算結果を取得
print(LST.prod(2,5)) # 5
print(LST.prod(3,7)) # 6


# LST.prod(left,x)がgを満たす最大のxを二分探索
left = 0
g = lambda x:x<5
print(LST.max_right(left , g)) # 5

区間更新・区間最大値取得

from atcoder.lazysegtree import LazySegTree

# 値の2項演算
def op(value1, value2):
    return max(value1, value2)

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return value if f is id_ else f

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return g if f is id_ else f

# 値の単位元
e = -float('inf')

# 作用素の単位元
id_ = None

l = [0,1,2,3,4,5,6]
LST = LazySegTree(op, e, mapping, composition, id_, l)
使用例 
# [2,5)を5で更新
LST.apply(2,5,5) # [0,1,5,5,5,5,6]

# 区間の演算結果を取得
print(LST.prod(2,5)) # 5
print(LST.prod(3,7)) # 6


# LST.prod(left, x)がgを満たす最大のxを二分探索
left = 0
g = lambda x:x is None or x<5
print(LST.max_right(left , g)) # 2

区間加算・区間最小値取得

from atcoder.lazysegtree import LazySegTree

INF = float('INF')

# 値の2項演算
def op(value1, value2):
    return min(value1, value2)

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return f + value

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return f + g

# 値の単位元
e = INF

# 作用素の単位元
id_ = 0

l = [0,1,2,3,4,5,6]
LST = LazySegTree(op, e, mapping, composition, id_, l)
使用例 

# [2,5)に1加算
LST.apply(2,5,1)

# 区間の演算結果を取得
print(LST.prod(2,5)) # 3
print(LST.prod(3,7)) # 4


# LST.prod(x, right)がgを満たす最小のxを二分探索
right = 6
g = lambda x:x>1
print(LST.min_left(right , g)) # 2

区間更新・区間最小値取得

from atcoder.lazysegtree import LazySegTree

# 値の2項演算
def op(value1, value2):
    return min(value1, value2)

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return value if f is id_ else f

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return g if f is id_ else f

# 値の単位元
e = float('inf')

# 作用素の単位元
id_ = None

l = [0,1,2,3,4,5,6]
LST = LazySegTree(op, e, mapping, composition, id_, l)
使用例 
# [2,5)を10で更新
LST.apply(2,5,10) # [0,1,10,10,10,5,6]

# 区間の演算結果を取得
print(LST.prod(2,5)) # 10
print(LST.prod(3,7)) # 5


# LST.prod(left, x)がgを満たす最大のxを二分探索
left = 2
g = lambda x:x is e or x>5
print(LST.max_right(left , g)) # 5

区間加算・区間和取得

from atcoder.lazysegtree import LazySegTree

# 値の2項演算
def op(value1, value2):
    return [value1[0]+value2[0],value1[1]+value2[1]]

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return [value[0],value[1]+f*value[0]]

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return f+g

# 値の単位元
e = [0,0]

# 作用素の単位元
id_ = 0

l = [0,1,2,3,4,5,6]

# 区間和取得の場合は[区間のサイズ, 値]として扱う
l = [[1,value] for value in l]
LST = LazySegTree(op, e, mapping, composition, id_, l)
使用例 
# [2,5)に3を加算
LST.apply(2,5,3) # [0,1,5,6,7,5,6]

# 区間の演算結果を取得
print(LST.prod(2,5)) # [3,18]
print(LST.prod(3,7)) # [4,24]

# LST.prod(left, x)がgを満たす最大のxを二分探索
left = 0
g = lambda x: x[1]<15
print(LST.max_right(left , g)) # 4

区間更新・区間和取得

from atcoder.lazysegtree import LazySegTree

# 値の2項演算
def op(value1, value2):
    return [value1[0]+value2[0],value1[1]+value2[1]]

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    if f is id_:return value
    return [value[0],f*value[0]]

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return g if f is id_ else f

# 値の単位元
e = [0,0]

# 作用素の単位元
id_ = None

l = [0,1,2,3,4,5,6]

# 区間和取得の場合は[区間のサイズ, 値]として扱う
l = [[1,value] for value in l]
LST = LazySegTree(op, e, mapping, composition, id_, l)
使用例 
# [2,5)を3で更新
LST.apply(2,5,3) # [0,1,3,3,3,5,6]

# 区間の演算結果を取得
print(LST.prod(2,5)) # [3,9]
print(LST.prod(3,7)) # [4,17]

# LST.prod(left, x)がgを満たす最大のxを二分探索
left = 0
g = lambda x: x[1]<15
print(LST.max_right(left , g)) # 5

おまけ・カスタマイズするには？

演算に必要な特性

必要な特性は以下の二点です。

  1. セグメントツリーと同様区間演算がモノイドを成すこと
  2. 区間の値を変更する操作において、区間演算の結果が効率的に計算できること

例：区間加算・区間和取得

  1. 区間演算は足し算なのでこれはモノイドを成します
  2. 区間加算を行うと区間の和は 加算する値 x 区間のサイズ となり区間のサイズがわかれば計算できます。

上記の結果から値には一緒にサイズも持たせることにします。
上記のサンプルではリストで書いていますが、以下では可読性のためにクラスを作ることにします。
全体像を示した後に説明します。

from atcoder.lazysegtree import LazySegTree

class S:
    def __init__(self,size=0,value=0):
        self.size=size
        self.value=value

# 値の2項演算
def op(value1, value2):
    return S(
            size  = value1.size + value2.size,
            value = value1.value + value2.value
            )

# 上のブロックの作用素を下のブロックの値に伝播
def mapping(f, value):
    return S(
            size = value.size,
            value = value.value + value.size*f
            )

# 上のブロックの作用素を下のブロックの作用素に伝播
def composition(f, g):
    return f+g

# 値の単位元
e = S(size=0, value=0)

# 作用素の単位元
id_ = 0

値とサイズを持つクラスSを定義しました。

class S:
    def __init__(self,size=0,value=0):
        self.size=size
        self.value=value

通常のセグメントツリー同様opを定義します。今回はサイズも持っているのでサイズの方も足し算しています。

def op(value1, value2):
    return S(
            size  = value1.size + value2.size,
            value = value1.value + value2.value
            )

次に区間に足し算する操作を定義します。中身の要素はわかりませんが、計算結果がvalueとなった区間に対しての区間加算操作を用意します。
例えば、中身はわからないけど合計が5で要素が3つである区間の要素すべてに3を足せば合計は 5 + 3*3 で合計値は14に変化します。
そのような操作をmappingという関数で実装します。

def mapping(f, value):
    return S(
            size = value.size,
            value = value.value + value.size*f
            )

さらに、作用素（将来的に足す値）同士の演算を定義します。
たとえば、「今後、これより下のすべての区間に5を足す」という操作がすでにある状態で、さらに「今後、これより下のすべての区間に6を足す」という操作が追加されたとします。
この場合、結果として「今後、これより下のすべての区間に11を足す」という単一の操作にまとめることができます。
このように、複数の操作をまとめて1つの操作に置き換えるしくみを composition と呼びます。

def composition(f, g):
    return f+g

最後に単位元を用意してあげれば準備完了です！お疲れさまでした

# 値の単位元
e = S(size=0, value=0)

# 作用素の単位元
id_ = 0

上記を踏まえて出来そうな演算とできなさそうな演算

ちょっといい例が思いつかないのですべてXOR取得の演算です。

できそうな演算

  1. 区間更新区間XOR取得
    a. XORはモノイドです
    b. 区間更新操作で区間のサイズの偶奇で区間xorの計算結果が予想できそう
  2. 区間XOR更新区間XOR取得
    a. XORはモノイドです
    b. XOR更新ならば、区間のサイズの偶奇で各bitに変更があるか確認ができそう

難しそうな演算

  1. 区間加算区間XOR取得
    a. 区間XORの結果が決まっていても区間内のすべてにXを加算をしたあとの値は定まりません
0
0
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
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?