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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <atcoder/lazysegtree>
#include <atcoder/modint>
#include <cstdio>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
struct S {
    mint a;
    int size;
};
struct F {
    mint a, b;
};
S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }
S e() { return S{0, 0}; }
S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }
F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }
F id() { return F{1, 0}; }
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<S> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        a[i] = S{x, 1};
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    for (int i = 0; i < q; i++) {
        int t;
        scanf("%d", &t);
        if (t == 0) {
            int l, r;
            int c, d;
            scanf("%d %d %d %d", &l, &r, &c, &d);
            seg.apply(l, r, F{c, d});
        } else {
            int l, r;
            scanf("%d %d", &l, &r);
            printf("%d\n", seg.prod(l, r).a.val());
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <atcoder/lazysegtree>
#include <atcoder/modint>
#include <cstdio>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
struct S {
    // # of 0 / # of 1 / inversion number
    long long zero, one, inversion;
};
// swapping flag
using F = bool;
S op(S l, S r) {
    return S{
        l.zero + r.zero,
        l.one + r.one,
        l.inversion + r.inversion + l.one * r.zero,
    };
}
S e() { return S{0, 0, 0}; }
S mapping(F l, S r) {
    if (!l) return r;
    // swap
    return S{r.one, r.zero, r.one * r.zero - r.inversion};
}
F composition(F l, F r) { return (l && !r) || (!l && r); }
F id() { return false; }
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<S> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (x == 0)
            a[i] = S{1, 0, 0};
        else
            a[i] = S{0, 1, 0};
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    for (int i = 0; i < q; i++) {
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r);
        l--;
        if (t == 1) {
            seg.apply(l, r, true);
        } else {
            printf("%lld\n", seg.prod(l, r).inversion);
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX