Lazy Segtree

モノイド $(S, \cdot: S \times S \to S, e \in S)$と、$S$ から $S$ への写像の集合 $F$ であって、以下の条件を満たすようなものについて使用できるデータ構造です。

$F$ は恒等写像 $\mathrm{id}$ を含む。つまり、任意の $x \in S$ に対し $\mathrm{id}(x) = x$ をみたす。
$F$ は写像の合成について閉じている。つまり、任意の $f, g \in F$ に対し $f \circ g \in F$ である。
任意の $f \in F, x, y \in S$ に対し $f(x \cdot y) = f(x) \cdot f(y)$ をみたす。

長さ $N$ の $S$ の配列に対し、

区間の要素に一括で $F$ の要素 $f$ を作用($x = f(x)$ )
区間の要素の総積の取得

を $O(\log N)$ で行うことが出来ます。詳細な要件は Appendix を参照してください。

また、このライブラリはオラクルとしてop, e, mapping, composition, idを使用しますが、これらが定数時間で動くものと仮定したときの計算量を記述します。オラクル内部の計算量が $O(f(n))$ である場合はすべての計算量が $O(f(n))$ 倍となります。

コンストラクタ

(1) var seg = initLazySegTree(n:int, op, e, mapping, composition, id)
    var seg = LazySegTreeType(S, F, op, e, mapping, composition, id).init(n)
    var seg = LazySegTree.getType(S, F, op, e, mapping, composition, id).init(n)
(2) var seg = initLazySegTree(v:seq[S], op, e, mapping, composition, id)
    var seg = LazySegTreeType(S, F, op, e, mapping, composition, id).init(v)
    var seg = LazySegTree.getType(S, F, op, e, mapping, composition, id).init(v)

モノイドの型 S
$\cdot: S \times S \to S$ を計算する関数 S op(S a, S b)
$e$ を返す関数 e():S
写像の型 F
$f(x)$ を返す関数 mapping(f:F, x:S):S
$f \circ g$ を返す関数 composition(f:F, f:F):F
$id$ を返す関数 id():F

を定義する必要があります。詳しくは、使用例やこちらも参照してください。

(1): 長さ n の数列 a を作ります。初期値は全部e()です。
(2): 長さ n = v.len の数列 a を作ります。v の内容が初期値となります。

制約

$0 \leq n \leq 10^8$

計算量

$O(n)$

set

seg.set(p:int, x:S):void
seg[p:int] = x:S

a[p] = x

制約

$0 \leq p < n$

計算量

$O(\log n)$

get

seg.get(p:int):S
seg[p:int]:S

a[p] を返します。

制約

$0 \leq p < n$

計算量

$O(\log n)$

prod

seg.prod(l..<r):S
seg[l..<r]:S

op(a[l], ..., a[r - 1]) を、モノイドの性質を満たしていると仮定して計算します。$l = r$ のときは e() を返します。

制約

$0 \leq l \leq r \leq n$

計算量

$O(\log n)$

all_prod

seg.all_prod():S

op(a[0], ..., a[n-1]) を計算します。$n = 0$ のときは e() を返します。

計算量

$O(1)$

apply

(1) seg.apply(p:int, f:F):void
(2) seg.apply(l..<r, f:F):void

(1) a[p] = f(a[p])
(2) i = l..r-1についてa[i] = f(a[i])

制約

(1) $0 \leq p < n$
(2) $0 \leq l \leq r \leq n$

計算量

$O(\log n)$

max_right

(1) seg.max_right(l:int, g:(S)->bool):int
(2💻) seg.max_right(l:int, g:(S)->bool):int

(1): 関数 g(x:S):bool を定義する必要があります。segtreeの上で二分探索をします。
(2): Sを引数にとりboolを返す関数オブジェクトを渡して使用します。

以下の条件を両方満たす r を(いずれか一つ)返します。

r = l もしくは g(op(a[l], a[l + 1], ..., a[r - 1])) = true
r = n もしくは g(op(a[l], a[l + 1], ..., a[r])) = false

gが単調だとすれば、g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r、と解釈することが可能です。

制約

gを同じ引数で呼んだ時、返り値は等しい(=副作用はない)
g(e()) = true
$0 \leq l \leq n$

計算量

$O(\log n)$

min_left

(1) seg.min_left(r:int, g:(S)->bool):int
(2💻) int seg.min_left(r:int, g:(S)->bool):int

(1): 関数 bool g(S x) を定義する必要があります。segtreeの上で二分探索をします。
(2): Sを引数にとりboolを返す関数オブジェクトを渡して使用します。

以下の条件を両方満たす l を(いずれか一つ)返します。

l = r もしくは g(op(a[l], a[l + 1], ..., a[r - 1])) = true
l = 0 もしくは g(op(a[l - 1], a[l], ..., a[r - 1])) = false

gが単調だとすれば、g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l、と解釈することが可能です。

制約

gを同じ引数で呼んだ時、返り値は等しい(=副作用はない)
g(e()) = true
$0 \leq r \leq n$

計算量

$O(\log n)$

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_k

import atcoder/header import atcoder/lazysegtree import atcoder/modint import sugar type mint = modint998244353 type S = tuple[a:mint, size:int] type F = tuple[a:mint, b:mint] let op = (l:S, r:S) => (l.a + r.a, l.size + r.size) let e = () => (mint(0), 0) let mapping = (l:F, r:S) => (r.a * l.a + r.size * l.b, r.size) let composition = (l:F, r:F) => (r.a * l.a, r.b * l.a + l.b) let id = () => (mint(1), mint(0)) let n, q = nextInt() var a = newSeq[S](n) for i in 0..<n: let x = nextInt() a[i] = (mint.init(x), 1) var seg = initLazySegTree(a, op, e, mapping, composition, id) for i in 0..<q: let t = nextInt() if t == 0: let l, r, c, d = nextInt() seg.apply(l..<r, (c.mint, d.mint)); else: let l, r = nextInt() echo seg.prod(l..<r).a.val()

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_l

include atcoder/header import atcoder/lazysegtree block: type S = tuple[zero, one, inversion:int] # swapping flag type F = bool proc op(l, r:S):S = (l.zero + r.zero, l.one + r.one, l.inversion + r.inversion + l.one * r.zero) proc e():S = (0,0,0) proc mapping(l:F, r:S):S = if not l: return r return (r.one, r.zero, r.one * r.zero - r.inversion) proc composition(l, r:F):F = (l and not r) or (not l and r) proc id():F = false let n, q = nextInt() var a = newSeq[S](n) for i in 0..<n: let x = nextInt() if x == 0: a[i] = (1, 0, 0) else: a[i] = (0, 1, 0) var seg = init_lazy_segtree(a, op, e, mapping, composition, id) for i in 0..<q: var t, l, r = nextInt() l.dec if t == 1: seg.apply(l..<r, true) else: echo seg.prod(l..<r).inversion

ActionMonoid記述子による構築

atcoder/extra/structure/monoid_segtreeをimportすると、 ActionMonoid記述子からLazySegTreeを構築できます。

useActionMonoid(
  RangeAddMax,
  AddMonoid,
  MaxMonoid,
  mapping,
)

var tree = RangeAddMax.initLazySegTree(values)

公開上は作用Monoid Fを値Monoid Sより先に記述します。作用合成composition(f, g)はf after gです。

従来のuseActedMonoid(Name, S, F, mapping)と callback constructorも維持されます。