Segtree / Lazy Segtree Tutorial

There are various types of segment trees. For example, some compute the sum of all elements in a given interval, while others compute the max. Our segtrees are designed in an abstract way; it works for all operations that satisfy certain algebraic properties. Let’s see their usage with various specific examples.

Segtree

First, let’s solve this task. For now, ignore queries of the third type.

We work on an integer sequence, and we are interested in maximums. Thus, naturally, our monoid \(S\) should be the set of integers (for the purpose of this task, let’s use only integers between \(-1\) and \(10^9\), and use \(\mathrm{int}\) to represent them), and its binary operation should be \(\max\). (Note that \(\cdot\) and the term “product” in the definition of monoid denotes an arbitrary operation; here \(a \cdot b\) means \(\max(a, b)\), and we call it “the product of \(a\) and \(b\)”.)

Let’s confirm that this way \(S\) becomes a monoid: - The maximum of two elements in \(S\) is always in \(S\), thus \(\max\) is a valid binary operation defined on \(S\). - \(\max(\max(a, b), c) = \max(a, \max(b, c))\), thus the associativity holds. - It has the identity element \(e = -1\): it satisfies \(\max(a, e) = \max(e, a) = a\) for any \(a \in S\).

Now let’s type these rules:

int op(int a, int b) { return max(a, b); }
int e() { return -1; }

And we can declare the segtree we want as follows:

segtree<int, op, e> seg(n); // n is the length of the segtree

If we ignore the queries of the third type, the entire code will be as follows:

#include <atcoder/segtree>
#include <cstdio>
#include <vector>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return max(a, b); }

int e() { return -1; }

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &(a[i]));
    }

    segtree<int, op, e> seg(a);

    for (int i = 0; i < q; i++) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x, v;
            scanf("%d %d", &x, &v);
            x--;
            seg.set(x, v);
        } else if (t == 2) {
            int l, r;
            scanf("%d %d", &l, &r);
            l--;
            printf("%d\n", seg.prod(l, r));
        }
    }
}

For the usage of the queries of the third type, please refer to the documentation.

Lazy Segtree

Now let’s consider this task. Here we assume that all \(c\) are zeroes, that is, all update queries are “multiply by a given constant”. We will describe the full solution in the next chapter.

This time, as we need to update multiple elements at once, we should use a lazy segtree. Naturally, \(S = \mathbb{F}_{p}\) (where \(p = 998244353\)), the binary operation on \(S\) is \(+\), and \(F\) is the set of all maps of the form \(f(x) = bx\) for some \(b \in S\).

Again, let’s confirm that \((S, F)\) satisfies the algebraic properties given in the document:

• \((S, +)\) forms a monoid with the identity element \(e = 0 \in S\).
• Each element of \(F\) is a mapping from \(S\) to \(S\).
• \(F\) contains an identity map given by \(b = 1\).
• \(F\) is closed under compositions. If we denote the parameter \(b\) of \(f\) as \(b_f\), \(f(g(x)) = (b_f b_g)x\), thus the parameter \(b\) of \(f \circ g\) is \(b_f b_g\).
• It’s easy to confirm that \(f(x) \cdot f(y) = f(x \cdot y)\) for all \(x, y \in S\) and \(f \in F\) (note that here \(\cdot\) actually denotes the addition; both are \(b_f(x + y)\)).

Let’s type these rules:

#define P 998244353

using S = long long;

struct F {
    long long b; // denotes the mapping "multiply by b"
};

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

S e() { return 0; }

S mapping(F f, S x) { return f.b * x % P; }

F composition(F f, F g) { return f.b * g.b % P; }

F id() { return F{1}; }

And we can declare the segtree we want as follows:

lazy_segtree<S, op, e, F, mapping, composition, id> seg(n); // n is the length of the segtree

The entire code will be as follows:

#include <atcoder/lazysegtree>
#include <atcoder/modint>
#include <cstdio>

using namespace std;
using namespace atcoder;

#define P 998244353

using S = long long;

struct F {
    long long b; // denotes the mapping "multiply by b"
};

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

S e() { return 0; }

S mapping(F f, S x) { return f.b * x % P; }

F composition(F f, F g) { return f.b * g.b % P; }

F id() { return F{1}; }

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] = x;
    }

    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 b, c;
            scanf("%d %d %d %d", &l, &r, &b, &c); // here we assume that c = 0
            seg.apply(l, r, F{b});
        } else {
            int l, r;
            scanf("%d %d", &l, &r);
            printf("%d\n", seg.prod(l, r));
        }
    }
}

Lazy Segtree (more advanced example)

Now we describe the full solution when \(c\) is not necessarily zero.

This time we can’t simply extend \(F\) to all maps of the form \(f(x) = bx + c\) because the condition \(f(x) \cdot f(y) = f(x \cdot y)\) doesn’t hold then. We need to find some other ways.

Here is a possible solution:

• \(S\) is the set of all sequences (of arbitrary finite length including zero) whose elements are in \(\mathbb{F}_{p}\).
• The binary operation on \(S\) is defined as a concatenation. For example, if \(x = (1, 6, 3)\) and \(y = (2, 3)\), \(x \cdot y = (1, 6, 3, 2, 3)\).
• Then \(S\) becomes a monoid with the identity element \(e = ()\) (an empty sequence).
• Elements of \(F\) are determined by two parameters \(b, c \in \mathbb{F}_{p}\), and it maps \((x_1, x_2, ...) \in S\) to \((b x_1 + c, b x_2 + c, ...)\).
• This way it’s easy to confirm that \((S, F)\) satisfy the given properties.

We can’t represent elements of \(S\) using \(\mathrm{vector}\) (then the oracle calls won’t be O(1) and the solution will be too slow). The key idea here is that for each element of \(S\), we only need to keep its length and the sum of all elements. In the solution below, \(a\) represents the sum of all elements, and \(size\) represents the length of the sequence.

#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());
        }
    }
}

Strictly speaking, the code above doesn’t satisfy the property of the algebraic structure because the lengths of the sequences of the underlying monoid can be arbitrary non-negative integers and may not fit into \(\mathrm{int}\). To handle this issue, please read [here]().

If you need more practice, please try this one.