SegTreeLazy< Monoid, Operator, mapping > 構造体テンプレート

遅延評価セグメント木 [詳解]

#include "segtree_lazy.hpp"

公開型
using	MonoidType = typename Monoid::Type
using	OperatorType = typename Operator::Type

公開メンバ関数
	SegTreeLazy ()=default
	SegTreeLazy (int n)
	要素数 n の遅延セグ木を構築する
	SegTreeLazy (const vector< MonoidType > &v)
	配列 v から遅延セグ木を構築する
void	set (int i, MonoidType x)
	i 番目の要素を x に更新する
void	apply (int l, int r, OperatorType x)
	区間 [l, r) に x を作用させる
MonoidType	fold (int l, int r)
	区間 [l, r) のモノイド積を返す
template<typename F>
int	find_right (int l, F f)
	区間 [l, x) のモノイド積が f を満たすような最大の x >= l を返す
template<typename F>
int	find_left (int r, F f)
	区間 [x, r) のモノイド積が f を満たすような最小の x<=r を返す
int	size ()
MonoidType	operator[] (int i)

詳解

template<typename Monoid, typename Operator, auto mapping>
struct SegTreeLazy< Monoid, Operator, mapping >

遅延評価セグメント木

テンプレート引数

Monoid	モノイド
Operator	作用素
mapping	（モノイドの元，作用素の元）→モノイドの元を返す関数

segtree_lazy.hpp の 9 行目に定義があります。

型定義メンバ詳解

MonoidType

template<typename Monoid, typename Operator, auto mapping>

using SegTreeLazy< Monoid, Operator, mapping >::MonoidType = typename Monoid::Type

segtree_lazy.hpp の 10 行目に定義があります。

OperatorType

template<typename Monoid, typename Operator, auto mapping>

using SegTreeLazy< Monoid, Operator, mapping >::OperatorType = typename Operator::Type

segtree_lazy.hpp の 11 行目に定義があります。

構築子と解体子

SegTreeLazy() [1/3]

template<typename Monoid, typename Operator, auto mapping>

SegTreeLazy< Monoid, Operator, mapping >::SegTreeLazy ( )

default

SegTreeLazy() [2/3]

template<typename Monoid, typename Operator, auto mapping>

SegTreeLazy< Monoid, Operator, mapping >::SegTreeLazy ( int n )

inline

要素数 n の遅延セグ木を構築する

segtree_lazy.hpp の 15 行目に定義があります。

SegTreeLazy() [3/3]

template<typename Monoid, typename Operator, auto mapping>

SegTreeLazy< Monoid, Operator, mapping >::SegTreeLazy ( const vector< MonoidType > & v )

inline

配列 v から遅延セグ木を構築する

segtree_lazy.hpp の 22 行目に定義があります。

関数詳解

set()

template<typename Monoid, typename Operator, auto mapping>

void SegTreeLazy< Monoid, Operator, mapping >::set ( int i, MonoidType x )

inline

i 番目の要素を x に更新する

segtree_lazy.hpp の 31 行目に定義があります。

apply()

template<typename Monoid, typename Operator, auto mapping>

void SegTreeLazy< Monoid, Operator, mapping >::apply ( int l, int r, OperatorType x )

inline

区間 [l, r) に x を作用させる

segtree_lazy.hpp の 40 行目に定義があります。

fold()

template<typename Monoid, typename Operator, auto mapping>

MonoidType SegTreeLazy< Monoid, Operator, mapping >::fold ( int l, int r )

inline

区間 [l, r) のモノイド積を返す

segtree_lazy.hpp の 62 行目に定義があります。

find_right()

template<typename Monoid, typename Operator, auto mapping>

template<typename F>

int SegTreeLazy< Monoid, Operator, mapping >::find_right ( int l, F f )

inline

区間 [l, x) のモノイド積が f を満たすような最大の x >= l を返す

注意

f(Monoid::id())=true が成り立つ必要がある

覚え書き

O(log(N))

segtree_lazy.hpp の 80 行目に定義があります。

find_left()

template<typename Monoid, typename Operator, auto mapping>

template<typename F>

int SegTreeLazy< Monoid, Operator, mapping >::find_left ( int r, F f )

inline

区間 [x, r) のモノイド積が f を満たすような最小の x<=r を返す

注意

f(Monoid::id())=true が成り立つ必要がある

覚え書き

O(log(N))

segtree_lazy.hpp の 119 行目に定義があります。

size()

template<typename Monoid, typename Operator, auto mapping>

int SegTreeLazy< Monoid, Operator, mapping >::size ( )

inline

segtree_lazy.hpp の 154 行目に定義があります。

operator[]()

template<typename Monoid, typename Operator, auto mapping>

MonoidType SegTreeLazy< Monoid, Operator, mapping >::operator[] ( int i )

inline

segtree_lazy.hpp の 155 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• data_structure/segtree_lazy.hpp