Fenwick tree over an arbitrary abelian group. More...

#include <tpl_fenwick_tree.H>

Inheritance diagram for Aleph::Gen_Fenwick_Tree< T, Plus, Minus >:

Collaboration diagram for Aleph::Gen_Fenwick_Tree< T, Plus, Minus >:

Public Types
using	Item_Type = T
	The type of element stored in the tree.

Public Member Functions
	Gen_Fenwick_Tree (const size_t num, Plus pop=Plus(), Minus mop=Minus())
	Construct a tree with `num` elements, all equal to the identity `T()`.

	Gen_Fenwick_Tree (std::initializer_list< T > il, Plus pop=Plus(), Minus mop=Minus())
	Construct from an initializer list in O(n) time.

	Gen_Fenwick_Tree (const Array< T > &values, Plus pop=Plus(), Minus mop=Minus())
	Construct from an Array<T> in O(n) time.

	Gen_Fenwick_Tree (const std::vector< T > &values, Plus pop=Plus(), Minus mop=Minus())
	Construct from a std::vector<T> in O(n) time.

	Gen_Fenwick_Tree (const DynList< T > &values, Plus pop=Plus(), Minus mop=Minus())
	Construct from a DynList<T> in O(n) time.

	Gen_Fenwick_Tree (const Gen_Fenwick_Tree &)=default

	Gen_Fenwick_Tree (Gen_Fenwick_Tree &&) noexcept=default

Gen_Fenwick_Tree &	operator= (const Gen_Fenwick_Tree &)=default

Gen_Fenwick_Tree &	operator= (Gen_Fenwick_Tree &&) noexcept=default

void	update (size_t i, const T &delta)
	Point update: `a[i] = Plus(a[i], delta)`.

T	prefix (size_t i) const
	Prefix query: `Plus(a[0], a[1], ..., a[i])`.

T	query (const size_t l, const size_t r) const
	Range query: `Plus(a[l], a[l+1], ..., a[r])`.

T	get (const size_t i) const
	Retrieve the logical value `a[i]`.

void	set (const size_t i, const T &value)
	Set `a[i] = value`.

constexpr size_t	size () const noexcept
	Number of logical elements.

constexpr bool	is_empty () const noexcept
	True if the tree contains no elements.

Array< T >	values () const
	Reconstruct all original values into an Array.

void	swap (Gen_Fenwick_Tree &other) noexcept
	Swap this tree with `other` in O(1).

Protected Member Functions
void	build ()
	O(n) bottom-up construction of the tree array from raw values already placed in tree[1..n].

template<class F >
void	fill_from_indexed (F getter)
	Fill the internal storage from a 0-based indexed getter and build.

template<class StdIt >
void	fill_from_std_iter (StdIt first, StdIt last)
	Fill the internal storage from a standard iterator range and build.

template<class AlephIt >
void	fill_from_aleph_it (AlephIt it)
	Fill the internal storage from an Aleph-style iterator (get_it()) and build.

Static Protected Member Functions
static constexpr size_t	lowbit (size_t x) noexcept
	Return the least significant set bit of `x` (as a mask).

Protected Attributes
Array< T >	tree

size_t	n = 0

Plus	plus_op

Minus	minus_op

Detailed Description

template<typename T, class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>
requires (FenwickBinaryOp<Plus, T> && FenwickBinaryOp<Minus, T>)
class Aleph::Gen_Fenwick_Tree< T, Plus, Minus >

Fenwick tree over an arbitrary abelian group.

Maintains an implicit array a[0..n-1] and a companion tree array so that prefix queries a[0] + a[1] + ... + a[i] and point updates a[i] += delta are answered in O(log n).

The group is specified through two binary functors:

Plus(a, b) — the group operation (must be associative and commutative).
Minus(a, b) — the group subtraction, i.e. Plus(Minus(a, b), b) == a.

The identity element is assumed to be T() (the value produced by the default constructor).

Template Parameters

T	element type.
Plus	binary functor for the group operation.
Minus	binary functor for the inverse operation.

Example: // XOR Fenwick tree

struct Xor { int operator()(int a, int b) const { return a ^ b; } };

Gen_Fenwick_Tree<int, Xor, Xor> ft(10); // XOR is its own inverse

ft.update(3, 7);

int pfx = ft.prefix(5);

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466

Definition at line 139 of file tpl_fenwick_tree.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

using Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Item_Type = T

The type of element stored in the tree.

Definition at line 198 of file tpl_fenwick_tree.H.

Constructor & Destructor Documentation

◆ Gen_Fenwick_Tree() [1/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree	(	const size_t	num,
		Plus	pop = `Plus()`,
		Minus	mop = `Minus()`
	)

inline

Construct a tree with num elements, all equal to the identity T().

Parameters

num	number of elements.
pop	group operation functor.
mop	group subtraction functor.

Definition at line 207 of file tpl_fenwick_tree.H.

◆ Gen_Fenwick_Tree() [2/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree	(	std::initializer_list< T >	il,
		Plus	pop = `Plus()`,
		Minus	mop = `Minus()`
	)

inline

Construct from an initializer list in O(n) time.

Example: Gen_Fenwick_Tree<int> ft = {3, 1, 4, 1, 5};

assert(ft.prefix(2) == 8); // 3 + 1 + 4

Aleph::Gen_Fenwick_Tree
Fenwick tree over an arbitrary abelian group.
Definition tpl_fenwick_tree.H:140

Definition at line 223 of file tpl_fenwick_tree.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ Gen_Fenwick_Tree() [3/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree	(	const Array< T > &	values,
		Plus	pop = `Plus()`,
		Minus	mop = `Minus()`
	)

inline

Construct from an Array<T> in O(n) time.

Parameters

values	source array with the initial element values.
pop	group operation functor.
mop	group subtraction functor.

Definition at line 237 of file tpl_fenwick_tree.H.

◆ Gen_Fenwick_Tree() [4/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree	(	const std::vector< T > &	values,
		Plus	pop = `Plus()`,
		Minus	mop = `Minus()`
	)

inline

Construct from a std::vector<T> in O(n) time.

This overload is intentionally provided as STL-interoperability convenience. Aleph containers remain the primary API surface.

Parameters

values	source vector with the initial element values.
pop	group operation functor.
mop	group subtraction functor.

Definition at line 254 of file tpl_fenwick_tree.H.

◆ Gen_Fenwick_Tree() [5/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree	(	const DynList< T > &	values,
		Plus	pop = `Plus()`,
		Minus	mop = `Minus()`
	)

inline

Construct from a DynList<T> in O(n) time.

Parameters

values	source list with the initial element values.
pop	group operation functor.
mop	group subtraction functor.

Definition at line 268 of file tpl_fenwick_tree.H.

References LocateFunctions< Container, Type >::get_it().

◆ Gen_Fenwick_Tree() [6/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree ( const Gen_Fenwick_Tree< T, Plus, Minus > & )

default

◆ Gen_Fenwick_Tree() [7/7]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::Gen_Fenwick_Tree ( Gen_Fenwick_Tree< T, Plus, Minus > && )

defaultnoexcept

Member Function Documentation

◆ build()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::build ( )

inlineprotected

O(n) bottom-up construction of the tree array from raw values already placed in tree[1..n].

Definition at line 160 of file tpl_fenwick_tree.H.

◆ fill_from_aleph_it()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

template<class AlephIt >

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::fill_from_aleph_it ( AlephIt it )

inlineprotected

Fill the internal storage from an Aleph-style iterator (get_it()) and build.

Definition at line 188 of file tpl_fenwick_tree.H.

◆ fill_from_indexed()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

template<class F >

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::fill_from_indexed ( F getter )

inlineprotected

Fill the internal storage from a 0-based indexed getter and build.

Definition at line 169 of file tpl_fenwick_tree.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ fill_from_std_iter()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

template<class StdIt >

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::fill_from_std_iter	(	StdIt	first,
		StdIt	last
	)

inlineprotected

Fill the internal storage from a standard iterator range and build.

Definition at line 178 of file tpl_fenwick_tree.H.

◆ get()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

T Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::get ( const size_t i ) const

inline

Retrieve the logical value a[i].

Equivalent to query(i, i). O(log n).

Parameters

i	0-based index.

Exceptions

std::out_of_range if i >= size().

Definition at line 340 of file tpl_fenwick_tree.H.

◆ is_empty()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

constexpr bool Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::is_empty ( ) const

inlineconstexprnoexcept

True if the tree contains no elements.

Definition at line 362 of file tpl_fenwick_tree.H.

◆ lowbit()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

static constexpr size_t Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::lowbit ( size_t x )

inlinestaticconstexprprotectednoexcept

Return the least significant set bit of x (as a mask).

This is the classic Fenwick-tree "lowbit" helper. Implemented using only well-defined unsigned arithmetic to avoid relying on signed-style negation of a size_t.

Definition at line 153 of file tpl_fenwick_tree.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator=() [1/2]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Gen_Fenwick_Tree & Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::operator= ( const Gen_Fenwick_Tree< T, Plus, Minus > & )

default

◆ operator=() [2/2]

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Gen_Fenwick_Tree & Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::operator= ( Gen_Fenwick_Tree< T, Plus, Minus > && )

defaultnoexcept

◆ prefix()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

T Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::prefix ( size_t i ) const

inline

Prefix query: Plus(a[0], a[1], ..., a[i]).

Parameters

i	0-based index.

Returns: accumulated value from index 0 through i (inclusive).

Exceptions

std::out_of_range if i >= size().

Definition at line 305 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if.

Referenced by TEST().

◆ query()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

T Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::query	(	const size_t	l,
		const size_t	r
	)		const

inline

Range query: Plus(a[l], a[l+1], ..., a[r]).

Parameters

l	0-based left index (inclusive).
r	0-based right index (inclusive).

Returns: accumulated value over [l, r].

Exceptions

std::out_of_range if l > r or r >= size().

Definition at line 323 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if, l, Aleph::prefix(), and r.

◆ set()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::set	(	const size_t	i,
		const T &	value
	)

inline

Set a[i] = value.

Computes the required delta and calls update(). O(log n).

Parameters

i	0-based index.
value	new value for position i.

Exceptions

std::out_of_range if i >= size().

Definition at line 353 of file tpl_fenwick_tree.H.

References value.

Referenced by TEST().

◆ size()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

constexpr size_t Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::size ( ) const

inlineconstexprnoexcept

Number of logical elements.

Definition at line 359 of file tpl_fenwick_tree.H.

Referenced by TEST().

◆ swap()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::swap ( Gen_Fenwick_Tree< T, Plus, Minus > & other )

inlinenoexcept

Swap this tree with other in O(1).

Definition at line 377 of file tpl_fenwick_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::swap().

Referenced by TEST().

◆ update()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

void Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::update	(	size_t	i,
		const T &	delta
	)

inline

Point update: a[i] = Plus(a[i], delta).

Parameters

i	0-based index.
delta	value to add.

Exceptions

std::out_of_range if i >= size().

Definition at line 290 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if.

Referenced by TEST().

◆ values()

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Array< T > Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::values ( ) const

inline

Reconstruct all original values into an Array.

O(n log n) in the general case.

Definition at line 368 of file tpl_fenwick_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::create().

Member Data Documentation

◆ minus_op

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Minus Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::minus_op

protected

Definition at line 146 of file tpl_fenwick_tree.H.

◆ n

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

size_t Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::n = 0

protected

Definition at line 143 of file tpl_fenwick_tree.H.

◆ plus_op

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Plus Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::plus_op

protected

Definition at line 145 of file tpl_fenwick_tree.H.

◆ tree

template<typename T , class Plus = Aleph::plus<T>, class Minus = Aleph::minus<T>>

Array<T> Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::tree

protected

Definition at line 142 of file tpl_fenwick_tree.H.

The documentation for this class was generated from the following file:

tpl_fenwick_tree.H

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Item_Type

Constructor & Destructor Documentation

◆ Gen_Fenwick_Tree() [1/7]

◆ Gen_Fenwick_Tree() [2/7]

◆ Gen_Fenwick_Tree() [3/7]

◆ Gen_Fenwick_Tree() [4/7]

◆ Gen_Fenwick_Tree() [5/7]

◆ Gen_Fenwick_Tree() [6/7]

◆ Gen_Fenwick_Tree() [7/7]

Member Function Documentation

◆ build()

◆ fill_from_aleph_it()

◆ fill_from_indexed()

◆ fill_from_std_iter()

◆ get()

◆ is_empty()

◆ lowbit()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ prefix()

◆ query()

◆ set()

◆ size()

◆ swap()

◆ update()

◆ values()

Member Data Documentation

◆ minus_op

◆ n

◆ plus_op

◆ tree