Lazy Segtree

It is the data structure for the pair of a monoid $(S, \cdot: S \times S \to S, e \in S)$ and a set $F$ of $S \to S$ mappings that satisfies the following properties.

$F$ contains the identity map $\mathrm{id}$, where the identity map is the map that satisfies $\mathrm{id}(x) = x$ for all $x \in S$.
$F$ is closed under composition, i.e., $f \circ g \in F$ holds for all $f, g \in F$.
$f(x \cdot y) = f(x) \cdot f(y)$ holds for all $f \in F$ and $x, y \in S$.

Given an array $S$ of length $N$, it processes the following queries in $O(\log N)$ time (see Appendix for further details).

Acting the map $f\in F$ (cf. $x = f(x)$) on all the elements of an interval
Calculating the product of the elements of an interval

For simplicity, in this document, we assume that the oracles op, e, mapping, composition, and id work in constant time. If these oracles work in $O(T)$ time, each time complexity appear in this document is multipled by $O(T)$.

Constructor

(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);

The following should be defined.

The type S of the monoid
The binary operation S op(S a, S b)
The function S e() that returns $e$
The type F of the map
The function S mapping(F f, S x) that returns $f(x)$
The function F composition(F f, F g) that returns $f \circ g$
The function F id() that returns $\mathrm{id}$

See examples and here for further details.

(1): It creates an array a of length n. All the elements are initialized to e().
(2): It creates an array a of length n = v.size(), initialized to v.

Constraints

$0 \leq n \leq 10^8$

Complexity

$O(n)$

set

void seg.set(int p, S x)

a[p] = x

Constraints

$0 \leq p < n$

Complexity

$O(\log n)$

get

S seg.get(int p)

It returns a[p].

Constraints

$0 \leq p < n$

Complexity

$O(\log n)$

prod

S seg.prod(int l, int r)

It returns op(a[l], ..., a[r - 1]), assuming the properties of the monoid. It returns e() if $l = r$.

Constraints

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

Complexity

$O(\log n)$

all_prod

S seg.all_prod()

It returns op(a[0], ..., a[n - 1]), assuming the properties of the monoid. It returns e() if $n = 0$.

Complexity

$O(1)$

apply

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

(1) It applies a[p] = f(a[p]).
(2) It applies a[i] = f(a[i]) for all i = l..r-1.

Constraints

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

Complexity

$O(\log n)$

max_right

(1) int seg.max_right<g>(int l)
(2 ) int seg.max_right<G>(int l, G g)

(1): It applies a binary search on the segment tree. The function bool g(S x) should be defined.
(2): The function object that takes S as the argument and returns bool should be defined.

It returns an index r that satisfies both of the followings.

r = l or g(op(a[l], a[l + 1], ..., a[r - 1])) = true
r = n or g(op(a[l], a[l + 1], ..., a[r])) = false

If g is monotone, this is the maximum r that satisfies g(op(a[l], a[l + 1], ..., a[r - 1])) = true.

Constraints

if g is called with the same argument, it returns the same value, i.e., g has no side effect.
g(e()) = true
$0 \leq l \leq n$

Complexity

$O(\log n)$

min_left

(1) int seg.min_left<g>(int r)
(2 ) int seg.min_left<G>(int r, G g)

(1): It applies a binary search on the segment tree. The function bool g(S x) should be defined.
(2): The function object that takes S as the argument and returns bool should be defined.

It returns an index l that satisfies both of the following.

l = r or g(op(a[l], a[l + 1], ..., a[r - 1])) = true
l = 0 or g(op(a[l - 1], a[l], ..., a[r - 1])) = false

If g is monotone, this is the minimum l that satisfies g(op(a[l], a[l + 1], ..., a[r - 1])) = true.

Constraints

if g is called with the same argument, it returns the same value, i.e., g has no side effect.
g(e()) = true
$0 \leq r \leq n$

Complexity

$O(\log n)$

Examples

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