Segtree

モノイド $(S, \cdot: S \times S \to S, e \in S)$、つまり

を満たす代数構造に対し使用できるデータ構造です。

長さ $N$ の $S$ の配列に対し、

を $O(\log N)$ で行うことが出来ます。詳細な要件は Appendix を参照してください。

また、このライブラリはオラクルとしてop, eの2種類を使用しますが、これらが定数時間で動くものと仮定したときの計算量を記述します。オラクル内部の計算量が $O(f(n))$ である場合はすべての計算量が $O(f(n))$ 倍となります。

コンストラクタ

(1) segtree<S, op, e> seg(int n)
(2) segtree<S, op, e> seg(vector<S> v)

を定義する必要があります。例として、Range Min Queryならば

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

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

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

のようになります。

詳しくは、使用例や こちら も参照してください。

制約

計算量

set

void seg.set(int p, S x)

a[p]x を代入します。

制約

計算量

get

S seg.get(int p)

a[p] を返します。

制約

計算量

prod

S seg.prod(int l, int r)

op(a[l], ..., a[r - 1]) を、モノイドの性質を満たしていると仮定して計算します。$l = r$ のときは e() を返します。

制約

計算量

all_prod

S seg.all_prod()

op(a[0], ..., a[n - 1]) を計算します。$n = 0$ のときは e() を返します。

計算量

max_right

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

以下の条件を両方満たす r を(いずれか一つ)返します。

fが単調だとすれば、f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r、と解釈することが可能です。

制約

計算量

min_left

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

以下の条件を両方満たす l を(いずれか一つ)返します。

fが単調だとすれば、f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l、と解釈することが可能です。

制約

計算量

使用例

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