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

Fenwick Tree [詳解]

#include "fenwick_tree_abel.hpp"

公開型
using	Type = typename Abel::Type

公開メンバ関数
	FenwickTreeAbel ()=default
	FenwickTreeAbel (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 FenwickTreeAbel< Abel >

Fenwick Tree

テンプレート引数

Abel

可換群

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

型定義メンバ詳解

Type

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

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

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

構築子と解体子

FenwickTreeAbel() [1/2]

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

FenwickTreeAbel< Abel >::FenwickTreeAbel ( )

default

FenwickTreeAbel() [2/2]

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

FenwickTreeAbel< Abel >::FenwickTreeAbel ( int n )

inline

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

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

関数詳解

add()

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

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

inline

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

覚え書き

O(log(N))

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

sum()

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

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

inline

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

覚え書き

O(log(N))

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

operator[]()

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

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

inline

i 番目の要素を返す

覚え書き

O(log(N))

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

size()

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

int FenwickTreeAbel< Abel >::size ( )

inline

配列のサイズを返す

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

---

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

• data_structure/fenwick_tree_abel.hpp