# 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.

posted:
last update: