SparseTable< Band > 構造体テンプレート

スパーステーブル [詳解]

#include "sparse_table.hpp"

公開型
using	Type = typename Band::Type

公開メンバ関数
	SparseTable ()=default
	SparseTable (const vector< Type > &v)
	配列 v からスパーステーブルを構築する
Type	fold (int l, int r)
	区間 [l, r) の半群積を返す
int	size ()
Type	operator[] (int i) const

詳解

template<typename Band>
struct SparseTable< Band >

スパーステーブル

テンプレート引数

Band

冪等な半群

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

型定義メンバ詳解

Type

template<typename Band>

using SparseTable< Band >::Type = typename Band::Type

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

構築子と解体子

SparseTable() [1/2]

template<typename Band>

SparseTable< Band >::SparseTable ( )

default

SparseTable() [2/2]

template<typename Band>

SparseTable< Band >::SparseTable ( const vector< Type > & v )

inline

配列 v からスパーステーブルを構築する

覚え書き

O(N log(N))

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

関数詳解

fold()

template<typename Band>

Type SparseTable< Band >::fold ( int l, int r )

inline

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

sparse_table.hpp の 24 行目に定義があります。

size()

template<typename Band>

int SparseTable< Band >::size ( )

inline

sparse_table.hpp の 30 行目に定義があります。

operator[]()

template<typename Band>

Type SparseTable< Band >::operator[] ( int i ) const

inline

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

参照先 fold().

---

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

• data_structure/sparse_table.hpp