SqrtTree< Abel > 構造体テンプレート

更新 O(1) クエリ O(sqrt(N)) の改造版セグ木 [詳解]

#include "sqrt_tree.hpp"

公開型
using	Type = typename Abel::Type

公開メンバ関数
	SqrtTree ()=default
	SqrtTree (int n)
	SqrtTree (const vector< Type > &v)
	配列 v で初期化する
	SqrtTree (const vector< Type > &v, const vector< Type > &v_inv)
	配列 v とその逆元 v_inv で初期化する
void	set (int i, Type x)
	i 番目の要素を x に更新する
void	set (int i, Type x, Type x_inv)
	i 番目の要素を x に更新し、その逆元を x_inv に更新する
Type	fold (int l, int r)
	区間 [l, r) の群積を返す
Type	operator[] (int i) const
int	size () const

詳解

template<typename Abel>
struct SqrtTree< Abel >

更新 O(1) クエリ O(sqrt(N)) の改造版セグ木

Mo's Algorithmとの相性が良い

覚え書き

モノイドではなくアーベル群が乗る（モノイドや群の場合、更新が Θ(√N) でメリットがない） https://atcoder.jp/contests/abc405/submissions/65704867

sqrt_tree.hpp の 8 行目に定義があります。

型定義メンバ詳解

Type

template<typename Abel>

using SqrtTree< Abel >::Type = typename Abel::Type

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

構築子と解体子

SqrtTree() [1/4]

template<typename Abel>

SqrtTree< Abel >::SqrtTree ( )

default

SqrtTree() [2/4]

template<typename Abel>

SqrtTree< Abel >::SqrtTree ( int n )

inline

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

SqrtTree() [3/4]

template<typename Abel>

SqrtTree< Abel >::SqrtTree ( const vector< Type > & v )

inline

配列 v で初期化する

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

SqrtTree() [4/4]

template<typename Abel>

SqrtTree< Abel >::SqrtTree ( const vector< Type > & v, const vector< Type > & v_inv )

inline

配列 v とその逆元 v_inv で初期化する

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

関数詳解

set() [1/2]

template<typename Abel>

void SqrtTree< Abel >::set ( int i, Type x )

inline

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

覚え書き

O(f) （f : 逆元を求めるのにかかる計算量）

sqrt_tree.hpp の 53 行目に定義があります。

set() [2/2]

template<typename Abel>

void SqrtTree< Abel >::set ( int i, Type x, Type x_inv )

inline

i 番目の要素を x に更新し、その逆元を x_inv に更新する

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

fold()

template<typename Abel>

Type SqrtTree< Abel >::fold ( int l, int r )

inline

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

覚え書き

O(√N)

sqrt_tree.hpp の 72 行目に定義があります。

operator[]()

template<typename Abel>

Type SqrtTree< Abel >::operator[] ( int i ) const

inline

sqrt_tree.hpp の 86 行目に定義があります。

size()

template<typename Abel>

int SqrtTree< Abel >::size ( ) const

inline

sqrt_tree.hpp の 87 行目に定義があります。

---

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

• data_structure/sqrt_tree.hpp