Segtree

It is the data structure for monoids $(S, \cdot: S \times S \to S, e \in S)$, i.e., the algebraic structure 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 and e 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) segtree<S, op, e> seg(int n)
(2) segtree<S, op, e> seg(vector<S> v)

The following should be defined.

For example, for Range Minimum Query, the definitions are as follows.

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

int e() {
    return (int)(1e9);
}

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

See examples and here for further details.

Constraints

Complexity

set

void seg.set(int p, S x)

It assigns $x$ to a[p].

Constraints

Complexity

get

S seg.get(int p)

It returns a[p].

Constraints

Complexity

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

Complexity

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

max_right

(1) int seg.max_right<f>(int l)
(2) int seg.max_right<F>(int l, F f)

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

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

Constraints

Complexity

min_left

(1) int seg.min_left<f>(int r)
(2) int seg.min_left<F>(int r, F f)

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

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

Constraints

Complexity

Examples

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

#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 target; bool f(int v) { return v < target; } 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)); } else if (t == 3) { int p; scanf("%d %d", &p, &target); p--; printf("%d\n", seg.max_right<f>(p) + 1); } } }