はじめに

2023年8月にあった大幅なAtCoderの言語アップデートで、PythonにもACLとよばれる競プロライブラリが追加されました。

この記事では、その中の遅延セグメントツリーについてチートシートをまとめます。
組み合わせはすべてで $6$ 通りつくります。

区間演算クエリ
1. 加算: $A_i \leftarrow A_i + v \enspace (i=l,l+1,\cdots , r-1)$
2. 更新: $A_i \leftarrow v \enspace (i=l,l+1,\cdots , r-1)$
区間取得クエリ
1. 最小値: $\min$
2. 最大値: $\max$
3. 総和: $\text{sum}$

コンテスト中の人へ

次から自力で通せるように、あとでこの記事よんでね。

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

from atcoder.lazysegtree import LazySegTree

INF = 1 << 63


def op(ele1, ele2):
    return min(ele1, ele2)


def mapping(func, ele):
    return func + ele


def composition(func_upper, func_lower):
    return func_upper + func_lower


e = INF
id_ = 0

# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)

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

from atcoder.lazysegtree import LazySegTree

INF = 1 << 63


def op(ele1, ele2):
    return max(ele1, ele2)


def mapping(func, ele):
    return func + ele


def composition(func_upper, func_lower):
    return func_upper + func_lower


e = -INF
id_ = 0

# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)

3. 区間加算・区間和取得

from atcoder.lazysegtree import LazySegTree


def op(ele1, ele2):
    return ele1 + ele2


def mapping(func, ele):
    return func + ele


def composition(func_upper, func_lower):
    return func_upper + func_lower


e = 0
id_ = 0

# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)

4. 区間変更・区間最小値取得

from atcoder.lazysegtree import LazySegTree

INF = 1 << 63
ID = INF


def op(ele1, ele2):
    return min(ele1, ele2)


def mapping(func, ele):
    if func == ID:
        return ele
    else:
        return func


def composition(func_upper, func_lower):
    if func_upper == ID:
        return func_lower
    else:
        return func_upper


e = INF
id_ = ID

# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)

5. 区間変更・区間最大値取得

from atcoder.lazysegtree import LazySegTree

INF = 1 << 63
ID = INF


def op(ele1, ele2):
    return max(ele1, ele2)


def mapping(func, ele):
    if func == ID:
        return ele
    else:
        return func


def composition(func_upper, func_lower):
    if func_upper == ID:
        return func_lower
    else:
        return func_upper


e = -INF
id_ = ID

# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)

6. 区間変更・区間和取得

from atcoder.lazysegtree import LazySegTree

INF = 1 << 63
ID = INF


def op(ele1, ele2):
    return ele1 + ele2


def mapping(func, ele):
    if func == ID:
        return ele
    else:
        return func


def composition(func_upper, func_lower):
    if func_upper == ID:
        return func_lower
    else:
        return func_upper


e = 0
id_ = ID

# TODO (初期リストlst)
seg = LazySegTree(op, e, mapping, composition, id_, lst)

7. 簡易メソッド集

seg.apply(l, r, x) : 半開区間 $[l, r)$ の要素に対して、次の操作をする。
- 区間加算のとき: $A_i \leftarrow A_i + x \enspace (i=l, l+1, \cdots r-1)$
- 区間変更のとき: $A_i \leftarrow x \enspace (i=l, l+1, \cdots r-1)$
seg.prod(l, r) : 半開区間 $[l, r)$ の要素すべてについて、指定した区間取得方法(最大値取得や総和の取得など)で値を取得する。
seg.get(p) : $A_p$ の値を取得する。
seg.set(p, x) : $A_p \leftarrow x$ をする。

8. おわりに

上のコードでは $INF = 2^{63}$ としており、配列内の数値 $x$ は、 $-2^{63} \lt x \lt 2^{63}$ を満たしているとします。

遅延セグメントツリーは定数倍部分がそこそこ重いデータ構造で、想定解が遅延セグメントツリーでもPythonだと厳しいことがあります。

この記事は、次のアルメリアさんの記事から着想を得て参考にさせていただきました。ありがとうございます！