DynamicSegtree
(Data_structure/DynamicSegtree.hpp)
動的セグメント木 モノイドを渡す
コンストラクタ
(1) DynamicSegtree<Monoid> seg
(2) DynamicSegtree<Monoid> seg(long long N)
- (1): 上限が
LONG_LONG_MAX / 2
の、初期値がすべてM::e()
のセグメント木を作る。この場合、以降N = LONG_LONG_MAX / 2
とする。
- (2): 上限が
N
の、初期値がすべてM::e()
のセグメント木を作る
計算量
set
void seg.set(long long p, Monoid::T x)
``a[p]に
x`を代入する。
制約
- $0 \leq p < \text{limit}$
計算量
get
Monoid::T seg.get(long long p)
a[p]
の値を取得する。
制約
計算量
prod
Monoid::T seg.prod(long long l, long long r)
Monoid::op(a[l], ..., a[r-1])
を返す。$l = r$の時はMonoid::e()
が返る。
制約
計算量
all_prod
Monoid::op(a[0], ..., a[N-1])
を返す。
計算量
使いそうなモノイド
加法モノイド(区間和取得)
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