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.
Given an array $S$ of length $N$, it processes the following queries in $O(\log N)$ time (see Appendix for further details).
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)$.
(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.
S
of the monoidS op(S a, S b)
S e()
that returns $e$F
of the mapS mapping(F f, S x)
that returns $f(x)$F composition(F f, F g)
that returns $f \circ g$F id()
that returns $\mathrm{id}$See examples and here for further details.
a
of length n
. All the elements are initialized to e()
.a
of length n = v.size()
, initialized to v
.Constraints
Complexity
void seg.set(int p, S x)
a[p] = x
Constraints
Complexity
S seg.get(int p)
It returns a[p]
.
Constraints
Complexity
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
Complexity
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
(1) void seg.apply(int p, F f)
(2) void seg.apply(int l, int r, F f)
a[p] = f(a[p])
.a[i] = f(a[i])
for all i = l..r-1
.Constraints
Complexity
(1) int seg.max_right<g>(int l)
(2 ) int seg.max_right<G>(int l, G g)
bool g(S x)
should be defined. 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
g
is called with the same argument, it returns the same value, i.e., g
has no side effect.g(e()) = true
Complexity
(1) int seg.min_left<g>(int r)
(2 ) int seg.min_left<G>(int r, G g)
bool g(S x)
should be defined. 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
g
is called with the same argument, it returns the same value, i.e., g
has no side effect.g(e()) = true
Complexity