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::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

Definition at line 143 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 202 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 211 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:144

Definition at line 227 of file tpl_fenwick_tree.H.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), and Aleph::maps().

◆ 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 241 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 258 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 272 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 164 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 192 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 173 of file tpl_fenwick_tree.H.

References Aleph::maps().

◆ 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 182 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 344 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 366 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 157 of file tpl_fenwick_tree.H.

References Aleph::maps().

◆ 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 309 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 327 of file tpl_fenwick_tree.H.

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

◆ 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 357 of file tpl_fenwick_tree.H.

◆ 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 363 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 381 of file tpl_fenwick_tree.H.

References Aleph::maps(), 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 294 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if.

◆ 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 372 of file tpl_fenwick_tree.H.

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

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 150 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 147 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 149 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 146 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