SegTree< Monoid > 構造体テンプレート

セグメント木 [詳解]

#include "segtree.hpp"

公開型
using	Type = typename Monoid::Type

公開メンバ関数
	SegTree ()=default
	SegTree (int n)
	要素数 n のセグ木を構築する
	SegTree (const vector< Type > &v)
	配列 v からセグ木を構築する
void	set (int i, Type x)
	i 番目の要素を x に変更する
Type	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 を返す
Type	operator[] (int i)
	i 番目の要素を返す
int	size ()
	配列のサイズを返す

詳解

template<typename Monoid>
struct SegTree< Monoid >

セグメント木

segtree.hpp の 6 行目に定義があります。

型定義メンバ詳解

Type

template<typename Monoid>

using SegTree< Monoid >::Type = typename Monoid::Type

segtree.hpp の 7 行目に定義があります。

構築子と解体子

SegTree() [1/3]

template<typename Monoid>

SegTree< Monoid >::SegTree ( )

default

SegTree() [2/3]

template<typename Monoid>

SegTree< Monoid >::SegTree ( int n )

inline

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

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

SegTree() [3/3]

template<typename Monoid>

SegTree< Monoid >::SegTree ( const vector< Type > & v )

inline

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

覚え書き

O(N)

segtree.hpp の 19 行目に定義があります。

関数詳解

set()

template<typename Monoid>

void SegTree< Monoid >::set ( int i, Type x )

inline

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

覚え書き

O(log(N))

segtree.hpp の 29 行目に定義があります。

fold()

template<typename Monoid>

Type SegTree< Monoid >::fold ( int l, int r )

inline

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

覚え書き

O(log(N))

segtree.hpp の 37 行目に定義があります。

find_right()

template<typename Monoid>

template<typename F>

int SegTree< Monoid >::find_right ( int l, F f )

inline

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

注意

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

覚え書き

O(log(N))

segtree.hpp の 52 行目に定義があります。

find_left()

template<typename Monoid>

template<typename F>

int SegTree< Monoid >::find_left ( int r, F f )

inline

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

注意

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

覚え書き

O(log(N))

segtree.hpp の 88 行目に定義があります。

operator[]()

template<typename Monoid>

Type SegTree< Monoid >::operator[] ( int i )

inline

i 番目の要素を返す

覚え書き

O(1)

segtree.hpp の 122 行目に定義があります。

size()

template<typename Monoid>

int SegTree< Monoid >::size ( )

inline

配列のサイズを返す

segtree.hpp の 125 行目に定義があります。

---

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

• data_structure/segtree.hpp