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

Fenwick Tree [詳解]

#include "fenwick_tree.hpp"

公開型
using	Type = typename Abel::Type

公開メンバ関数
	FenwickTree ()=default
	FenwickTree (int n)
void	add (int i, ll x)
ll	sum (int l, int r)
ll	operator[] (int i)
int	size ()
	FenwickTree ()=default
	FenwickTree (int n)
	サイズ n のFenwick Treeを構築する
void	add (int i, Type x)
	i 番目の要素に対し v[i] <- op(v[i], x) と更新する
Type	sum (int l, int r)
	区間 [l, r) の群積を返す
Type	operator[] (int i)
	i 番目の要素を返す
int	size ()
	配列のサイズを返す

詳解

template<typename Abel = Abel::Sum<ll>>
struct FenwickTree< Abel >

Fenwick Tree

テンプレート引数

Abel

可換群

fenwick_tree.hpp の 4 行目に定義があります。

型定義メンバ詳解

Type

template<typename Abel = Abel::Sum<ll>>

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

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

構築子と解体子

FenwickTree() [1/4]

template<typename Abel = Abel::Sum<ll>>

FenwickTree< Abel >::FenwickTree ( )

default

FenwickTree() [2/4]

template<typename Abel = Abel::Sum<ll>>

FenwickTree< Abel >::FenwickTree ( int n )

inline

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

FenwickTree() [3/4]

template<typename Abel = Abel::Sum<ll>>

FenwickTree< Abel >::FenwickTree ( )

default

FenwickTree() [4/4]

template<typename Abel = Abel::Sum<ll>>

FenwickTree< Abel >::FenwickTree ( int n )

inline

サイズ n のFenwick Treeを構築する

fenwick_tree_abel.hpp の 16 行目に定義があります。

関数詳解

add() [1/2]

template<typename Abel = Abel::Sum<ll>>

void FenwickTree< Abel >::add ( int i, ll x )

inline

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

sum() [1/2]

template<typename Abel = Abel::Sum<ll>>

ll FenwickTree< Abel >::sum ( int l, int r )

inline

fenwick_tree.hpp の 14 行目に定義があります。

operator[]() [1/2]

template<typename Abel = Abel::Sum<ll>>

ll FenwickTree< Abel >::operator[] ( int i )

inline

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

参照先 sum().

size() [1/2]

template<typename Abel = Abel::Sum<ll>>

int FenwickTree< Abel >::size ( )

inline

fenwick_tree.hpp の 16 行目に定義があります。

add() [2/2]

template<typename Abel = Abel::Sum<ll>>

void FenwickTree< Abel >::add ( int i, Type x )

inline

i 番目の要素に対し v[i] <- op(v[i], x) と更新する

覚え書き

O(log(N))

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

sum() [2/2]

template<typename Abel = Abel::Sum<ll>>

Type FenwickTree< Abel >::sum ( int l, int r )

inline

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

覚え書き

O(log(N))

fenwick_tree_abel.hpp の 35 行目に定義があります。

operator[]() [2/2]

template<typename Abel = Abel::Sum<ll>>

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

inline

i 番目の要素を返す

覚え書き

O(log(N))

fenwick_tree_abel.hpp の 41 行目に定義があります。

size() [2/2]

template<typename Abel = Abel::Sum<ll>>

int FenwickTree< Abel >::size ( )

inline

配列のサイズを返す

fenwick_tree_abel.hpp の 44 行目に定義があります。

---

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

• data_structure/fenwick_tree.hpp
• data_structure/fenwick_tree_abel.hpp