LazySegmentTree

template <class S, class F>
requires monoid<S> && monoid<F> && acts_on<F, typename S::value_type>
struct LazySegmentTree;

概要

遅延評価セグメント木

名前	説明
`S`	データのモノイド
`F`	作用素モノイド（op が作用素の合成、f が値への作用）

名前	説明	計算量
`(constructor)`	(1) 空の木を構築する (2) n要素をeで初期化する (3) 列vから構築する	(1) $O(1)$ (2) $O(n)$ (3) $O(n)$

名前	説明	計算量
`set`	k番目をvalへ変更する	$O(\log n)$
`at`	k番目の値を返す	$O(\log n)$
`get`	k番目の値を返す	$O(\log n)$
`apply`	(1) k番目にfを作用する (2) 半開区間[a,b)にfを作用する	$O(\log n)$
`prod`	半開区間[a,b)の積を返す	$O(\log n)$
`all_prod`	全要素の積を返す	$O(1)$
`max_right`	(1) lから右へ積がval以下である最大境界を返す (2) lから右へ述語gが真である最大境界を返す	$O(\log n)$
`min_left`	(1) rから左へ積がval以下である最小境界を返す (2) rから左へ述語gが真である最小境界を返す	$O(\log n)$

// (1)
LazySegmentTree();

// (2)
explicit LazySegmentTree(int _n, T e = S::id());

// (3)
explicit LazySegmentTree(const std::vector<T> &v);

(1) 空の木を構築する

(2) n要素をeで初期化する

(3) 列vから構築する

// (1)
void apply(int k, U f);

// (2)
void apply(int a, int b, U f);

(1) k番目にfを作用する

(2) 半開区間[a,b)にfを作用する

// (1)
int max_right(int l, T val);

// (2)
template <class G>
int max_right(int l, G g);

(1) lから右へ積がval以下である最大境界を返す

(2) lから右へ述語gが真である最大境界を返す

// (1)
int min_left(int r, T val);

// (2)
template <class G>
int min_left(int r, G g);

(1) rから左へ積がval以下である最小境界を返す

(2) rから左へ述語gが真である最小境界を返す