ACLセグ木・遅延セグ木典型的な演算のチートシート

#セグメント木

セグ木

code:C++

segtree<S, op, e> seg(N); // 長さ N 、要素すべて e で初期化

segtree<S, op, e> seg(A); // vector<S> A で初期化

code:rs

// モノイドを定義

struct M;

impl Monoid for M {

type S = /*...*/;

fn binary_operation(x: &Self::S, y: &Self::S) -> Self::S {

// ...

}

fn identity() -> Self::S {

// ...

}

let mut seg = Segtree::<M>::new(N); // 長さ N 、要素すべて identity() で初期化

let mut seg = Segtree::<M>::from(vec!/*...*/); // Vec から初期化

Range Min

code:C++

using S = long long;

S op(S x, S y) { return min({x, y}); }

S e() { return LLONG_MAX; }

code:rs

// なお、 Min<S> が定義されているが、これは S が数値の場合のみ

// 有理数の min

struct RangeMin;

impl Monoid for RangeMin {

type S = (i64, i64); // (a, b) => (a/b); b >= 0 (b=0 のとき ±INF)

fn binary_operation(&x: &Self::S, &y: &Self::S) -> Self::S {

std::cmp::min_by(x, y, |&(a, b), &(c, d)| (a * d).cmp(&(c * b)) )

}

fn identity() -> Self::S {

(1, 0)

}

Range Max

code:C++

using S = long long;

S op(S x, S y) { return max({x, y}); }

S e() { return -LLONG_MAX; }

code:rs

// なお、 Min<S> が定義されているが、これは S が数値の場合のみ

// 有理数の max

struct RangeMax;

impl Monoid for RangeMax {

type S = (i64, i64); // (a, b) => (a/b); b >= 0 (b=0 のとき ±INF)

fn binary_operation(&x: &Self::S, &y: &Self::S) -> Self::S {

std::cmp::max_by(x, y, |&(a, b), &(c, d)| (a * d).cmp(&(c * b)) )

}

fn identity() -> Self::S {

(1, 0)

}

Range Sum

code:C++

using S = long long;

S op(S x, S y) { return x + y; }

S e() { return 0; }

code:Rust

struct RangeSum;

impl Monoid for RangeSum {

type S = i64;

fn binary_operation(&x: &Self::S, &y: &Self::S) -> Self::S {

x + y

}

fn identity() -> Self::S {

}

整数の連結

$ 0～$ 9を載せ文字列として連結する

ローリングハッシュとかにも応用できる

$ (n, 10^{nの桁数})を乗せる

code:Rust

struct RangeStrInteger {

type S = (i64, i64);

fn binary_operation(&(a, b): &Self::S, &(c, d): &Self::S) -> Self::S {

(a * d + c, b * d)

}

fn identity() -> Self::S {

(0, 1)

}

Range Product

code:C++

using S = long long;

S op(S x, S y) { return x * y; } // オーバーフローに注意

S e() { return 1; }

Range Product mod p (0 あり)

なお、mod 合成数のときは、素因数分解して指数ごとに個数を持つ

$ 0の指数が$ 1以上なら$ 0とみなす

$ 0の指数というか$ pの指数と言った方が合っているかも

code:Rust

struct RangeProduct;

impl Monoid for RangeProduct {

type S = (i64, usize); // (0以外の積 mod p, 0の指数)

fn binary_operation(&(x, e): &Self::S, &(y, f): &Self::S) -> Self::S {

(x * y % MOD, e + f)

}

fn identity() -> Self::S {

(1, 0)

}

Range XOR

code:C++

using S = long long;

S op(S x, S y) { return x ^ y; }

S e() { return 0; }

Range OR

code:C++

using S = long long;

S op(S x, S y) { return x | y; }

S e() { return 0; }

Range AND

code:C++

using S = long long;

S op(S x, S y) { return x & y; }

S e() { return 9223372036854775807LL; }

Range GCD

code:C++

using S = long long;

S op(S x, S y) { return gcd(x, y); }

S e() { return 0; }

Range LCM

このまま$ \text{mod}をとることはできないので、実際には素因数分解することが多そう（そもそも間に合わなそう）

code:C++

using S = long long;

S op(S x, S y) { return lcm(x, y); } // オーバーフローに注意

S e() { return 1; }

遅延セグ木

code:C++

lazy_segtree<S, op, e, F, mapping, composition, id> seg(N); // 長さ N 、要素すべて e で初期化

lazy_segtree<S, op, e, F, mapping, composition, id> seg(A); // vector<S> A で初期化

Range {Min, Max} * Range {Chmin, Chmax, Add, Update}

Range {Min, Max} に以下をくっつけるだけ

Range Chmin

code:C++

using F = long long;

S mapping(F f, S x) { return min({f, x}); }

F composition(F f, F g) { return min({f, g}); }

F id() { return LLONG_MAX; }

Range Chmax

code:C++

using F = long long;

S mapping(F f, S x) { return max({f, x}); }

F composition(F f, F g) { return max({f, g}); }

F id() { return -LLONG_MAX; }

Range Add

code:C++

using F = long long;

S mapping(F f, S x) { return f + x; }

F composition(F f, F g) { return f + g; }

F id() { return 0; }

Range Update

code:C++

using F = pair<bool, long long>;

S mapping(F f, S x) { return f.first ? f.second : x; }

F composition(F f, F g) { return g.first ? g : f; }

F id() { return make_pair(false, 0); }

Range Sum * Range Add

初期化するときは、第二要素は$ 1

code:C++

using S = pair<long long, int>;

S op(S x, S y) { return make_pair(x.first + y.first, x.second + y.second); }

S e() { return make_pair(0, 0); }

using F = long long;

S mapping(F f, S x) { return make_pair(x.first + f * x.second, x.second); }

F composition(F f, F g) { return f + g; }

F id() { return 0; }

code:Rust

struct RangeSumWidth;

impl Monoid for RangeSumWidth {

type S = (i64, i64);

fn binary_operation(&(x, n): &Self::S, &(y, m): &Self::S) -> Self::S {

(x + y, n + m)

}

fn identity() -> Self::S {

(0, 0)

}

struct RangeSumRangeAdd;

impl MapMonoid for RangeSumRangeAdd {

type M = RangeSumWidth;

type F = i64;

fn mapping(&f: &Self::F, &(x, n): &<RangeSumWidth as Monoid>::S) -> <RangeSumWidth as Monoid>::S {

(x + f * n, n)

}

fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {

f + g

}

fn identity_map() -> Self::F {

}

Range Sum * Range Multiply

code:C++

using S = long long;

S op(S x, S y) { return x + y; }

S e() { return 0; }

using F = long long;

S mapping(F f, S x) { return x * f; }

F composition(F f, F g) { return f * g; } // オーバーフローに注意

F id() { return 1; }

Range Sum * Range Update

初期化するときは、第二要素は$ 1

code:C++

using S = pair<long long, int>;

S op(S x, S y) { return make_pair(x.first + y.first, x.second + y.second); }

S e() { return make_pair(0, 0); }

using F = pair<bool, long long>; // {変更, 値}

S mapping(F f, S x) { return f.first ? make_pair(f.second * x.second, x.second) : x; }

F composition(F f, F g) { return g.first ? g : f; }

F id() { return make_pair(false, 0); }

Range Sum * Range {Chmin, Chmax}

普通の遅延セグ木では不可能

Segment Tree Beats が必要

atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats - ひとなので

Range XOR * Range Update

初期化するときは、第二要素は$ 1

code:C++

using S = pair<long long, int>;

S op(S x, S y) { return make_pair(x.first ^ y.first, x.second + y.second); }

S e() { return make_pair(0, 0); }

using F = pair<bool, long long>;

S mapping(F f, S x) { return f.first ? make_pair(f.second * (x.second & 1), x.second) : x; }

F composition(F f, F g) { return g.first ? g : f; }

F id() { return make_pair(false, 0); }

Range XOR * Range XOR

初期化するときは、第二要素は$ 1

code:C++

using S = pair<long long, int>;

S op(S x, S y) { return make_pair(x.first ^ y.first, x.second + y.second); }

S e() { return make_pair(0, 0); }

using F = long long;

S mapping(F f, S x) { return make_pair(x.first ^ f * (x.second & 1), x.second); }

F composition(F f, F g) { return f ^ g; }

F id() { return 0; }

Range XOR * Range AND

code:C++

using S = long long;

S op(S x, S y) { return x ^ y; }

S e() { return 0; }

using F = long long;

S mapping(F f, S x) { return x & f; }

F composition(F f, F g) { return f & g; }

F id() { return 9223372036854775807LL; }

Range {AND, OR} * Range {AND, OR, Update}

Range {AND, OR} に以下を付け足すだけ

Range AND

code:C++

using F = long long;

S mapping(F f, S x) { return x & f; }

F composition(F f, F g) { return f & g; }

F id() { return 9223372036854775807LL; }

Range OR

code:C++

using F = long long;

S mapping(F f, S x) { return x | f; }

F composition(F f, F g) { return f | g; }

F id() { return 0; }

Range Update

code:C++

using F = pair<bool, long long>;

S mapping(F f, S x) { return f.first ? f.second : x; }

F composition(F f, F g) { return g.first ? g : f; }

F id() { return make_pair(false, 0); }

参考

https://betrue12.hateblo.jp/entry/2020/09/23/005940