SparseTableDisjoint< Semigroup > 構造体テンプレート

スパーステーブル（Disjoint） [詳解]

#include "sparse_table_disjoint.hpp"

公開型
using	Type = typename Semigroup::Type

公開メンバ関数
	SparseTableDisjoint ()=default
	SparseTableDisjoint (const vector< Type > &v)
	配列 v からDisjoint Sparse Tableを構築する
Type	fold (int l, int r)
	区間 [l, r) の半群積を返す
Type	operator[] (int i) const
	i 番目の要素を返す
int	size ()
	配列のサイズを返す

詳解

template<typename Semigroup>
struct SparseTableDisjoint< Semigroup >

スパーステーブル（Disjoint）

テンプレート引数

Semigroup

半群（結合則が成り立つこと）

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

型定義メンバ詳解

Type

template<typename Semigroup>

using SparseTableDisjoint< Semigroup >::Type = typename Semigroup::Type

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

構築子と解体子

SparseTableDisjoint() [1/2]

template<typename Semigroup>

SparseTableDisjoint< Semigroup >::SparseTableDisjoint ( )

default

SparseTableDisjoint() [2/2]

template<typename Semigroup>

SparseTableDisjoint< Semigroup >::SparseTableDisjoint ( const vector< Type > & v )

inline

配列 v からDisjoint Sparse Tableを構築する

覚え書き

O(N log(N))

sparse_table_disjoint.hpp の 12 行目に定義があります。

関数詳解

fold()

template<typename Semigroup>

Type SparseTableDisjoint< Semigroup >::fold ( int l, int r )

inline

区間 [l, r) の半群積を返す

覚え書き

O(1)

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

operator[]()

template<typename Semigroup>

Type SparseTableDisjoint< Semigroup >::operator[] ( int i ) const

inline

i 番目の要素を返す

sparse_table_disjoint.hpp の 39 行目に定義があります。

参照先 fold().

size()

template<typename Semigroup>

int SparseTableDisjoint< Semigroup >::size ( )

inline

配列のサイズを返す

sparse_table_disjoint.hpp の 42 行目に定義があります。

---

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

• data_structure/sparse_table_disjoint.hpp