はじめに

この記事では以下の遅延セグメント木をACLで実装する時のチートシートを示します。
言語はPythonです。

ACLについて

AtCoderのジャッジで使用可能な、競プロでよく使うテクニックがまとまったライブラリです。
導入はREADME.mdを参考にしてください。

ドキュメント（C++）

区間加算・区間最小値

from atcoder.lazysegtree import LazySegTree
def op(a, b): return min(a, b)
_e = 1<<60 # INFの値は適宜
def mapp(f, x): return f+x
def comp(f, g): return f+g
_id = 0
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列

verify

区間加算・区間最大値

from atcoder.lazysegtree import LazySegTree
def op(a, b): return max(a, b)
_e = -(1<<60)
def mapp(f, x): return f+x
def comp(f, g): return f+g
_id = 0
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列

区間加算・区間和

from atcoder.lazysegtree import LazySegTree
def op(a, b):
    a_size, a_sum = a
    b_size, b_sum = b
    return (a_size+b_size, a_sum+b_sum)
_e = (0, 0)
def mapp(f, x):
    x_size, x_sum = x
    return (x_size, x_sum+f*x_size)
def comp(f, g): return f+g
_id = 0
vv = [(1, vi) for vi in v] # vに初期化の配列
S = LazySegTree(op, _e, mapp, comp, _id, vv)

verify
結果が（区間のサイズ、区間和）の形で返ってくるので、２番目の要素を答えとする。

区間更新・区間最小値

from atcoder.lazysegtree import LazySegTree
def op(a, b): return min(a, b)
_e = 1<<60 # INFの値は適宜
def mapp(f, x): return x if f == _id else f
def comp(f, g): return g if f == _id else f
_id = 1<<61
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列

verify

区間更新・区間最大値

from atcoder.lazysegtree import LazySegTree
def op(a, b): return max(a, b)
_e = -(1<<60) # INFの値は適宜
def mapp(f, x): return x if f == _id else f
def comp(f, g): return g if f == _id else f
_id = 1<<61
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列

区間更新・区間和

from atcoder.lazysegtree import LazySegTree
def op(a, b):
    a_size, a_sum = a
    b_size, b_sum = b
    return (a_size+b_size, a_sum+b_sum)
_e = (0, 0)
def mapp(f, x):
    if f == _id: return x
    x_size, x_sum = x
    return (x_size, f*x_size)
def comp(f, g): return g if f == _id else f
_id = 1<<61
vv = [(1, vi) for vi in v] # vに初期化の配列
S = LazySegTree(op, _e, mapp, comp, _id, vv)

verify
結果が（区間のサイズ、区間和）の形で返ってくるので、２番目の要素を答えとする。

遅延セグ木の主なメソッド

問題を解くときに使うメソッドを挙げます。
説明の中で、セグ木上の$i$番目$(0\le i< N)$の要素を$A_i$と表します。

set(p, x)

$A_p$を$x$に変更します。

get(p)

$A_p$の要素を取得します。

apply(l, r, x)

$A_l ⋯ A_{r-1}$の範囲に$x$を演算します。
区間加算の場合は区間全体に$x$を加算、区間更新の場合は区間を全て$x$で更新します。

prod(l, r)

$op(A_l ⋯ A_{r-1})$の結果を取得します。
区間最小の場合は区間の最小値、区間和の場合は区間の合計を取得します。

おわりに

コンテスト中は時間が無いのでこの記事を見て良いですが、変なものをセグ木に乗せるためには内部の理解が必須です。
コンテスト後にデバッグ出力などをしながらこのコードが何をしているかをぜひ理解してください。
特に、区間更新・区間和などは正しくクエリに答えるため工夫をしています。

また、ここで出てこないセグ木上でできることとして、max_right、min_leftというものもあります。
遅延セグ木やセグ木自体の説明は他の方の記事が詳しいので、自分で調べてみてください。

参考

この記事は以下の記事のPython版として作成しました。

verifyに使ったサイト