Segtree
(Data_structure/Segtree.hpp)
セグメント木 モノイドを渡す
モノイド
集合 $S$ とその二項演算 $\cdot : S \times S \to S$ で、
- $\forall a, b, c \in S~~(a \cdot b) \cdot c = a \cdot (b \cdot c)$
- $\exist e \in S
\mathrm{s.t.}\forall a \in S~~ e \cdot a = a \cdot e = a$
を満たすとき、$(S, \cdot, e)$ をモノイドという。
例えば加法モノイドなら、次のように書く。
struct Add_M {
using T = long long;
static T e() { return 0; }
static T op(T x, T y) { return x + y; }
};
T
はモノイドの型名。e()
は単位元、op(T x, T y)
は二項演算を返すようにする。
コンストラクタ
(1) Segtree<Monoid> seg(int N)
(2) Segtree<Monoid> seg(vector<Monoid::T> v)
- (1): 長さ
N
ですべてMonoid::e()
の数列で初期化
- (2):
v
の内容で初期化
計算量
set
void seg.set(int p, Monoid::T x)
a[p]
にx
を代入する。
制約
計算量
get
a[p]
の値を取得する。
制約
計算量
prod
Monoid::T seg.prod(int l, int r)
Monoid::op(a[l], ..., a[r-1])
を返す。$l = r$の時はMonoid::e()
が返る。
制約
計算量
all_prod
Monoid::op(a[0], ..., a[n-1])
を返す。
計算量
TODO: セグ木上の二分探索
使いそうなモノイド
加法モノイド(区間和取得)
struct Add_M {
using T = long long;
static T e() { return 0; }
static T op(T x, T y) { return x + y; }
};
最大モノイド(区間最大取得)
struct Max_M {
using T = long long;
static T e() { return -INF; }
static T op(T x, T y) { return max(x, y); }
};
最小モノイド(区間最小取得)
struct Min_M {
using T = long long;
static T e() { return INF; }
static T op(T x, T y) { return min(x, y); }
};
テンプレート
struct Monoid {
using T = T;
static T e() { return e; }
static T op(T x, T y) { return op(x, y); }
}
Verified with
Code
Back to top page