Fenwick tree supporting range updates and range queries. More...

#include <tpl_fenwick_tree.H>

Public Types
using	Item_Type = T

Public Member Functions
	Range_Fenwick_Tree (const size_t num)
	Construct a tree with `num` elements, all zero.

	Range_Fenwick_Tree (std::initializer_list< T > il)
	Construct from an initializer list in O(n) time.

	Range_Fenwick_Tree (const Array< T > &values)
	Construct from an Array<T> in O(n) time.

	Range_Fenwick_Tree (const Range_Fenwick_Tree &)=default

	Range_Fenwick_Tree (Range_Fenwick_Tree &&) noexcept=default

Range_Fenwick_Tree &	operator= (const Range_Fenwick_Tree &)=default

Range_Fenwick_Tree &	operator= (Range_Fenwick_Tree &&) noexcept=default

void	update (size_t l, const size_t r, const T &delta)
	Range update: add `delta` to every `a[i]` with `l <= i <= r`.

void	point_update (const size_t i, const T &delta)
	Point update: add `delta` to `a[i]`.

T	prefix (const size_t i) const
	Prefix query: sum of `a[0..i]`.

T	query (const size_t l, const size_t r) const
	Range query: sum of `a[l..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 (Range_Fenwick_Tree &other) noexcept
	Swap this tree with `other` in O(1).

Private Member Functions
T	prefix_sum (size_t i) const
	Internal: prefix sum P(i) = (i+1)*B1.prefix(i) - B2.prefix(i)

void	build_from_diffs (const Array< T > &d)
	Rebuild b1 and b2 from a difference array stored in `d`.

Private Attributes
Gen_Fenwick_Tree< T >	b1

Gen_Fenwick_Tree< T >	b2

size_t	n = 0

Detailed Description

template<FenwickArithmetic T>
class Aleph::Range_Fenwick_Tree< T >

Fenwick tree supporting range updates and range queries.

Maintains an implicit array a[0..n-1] and supports adding a constant to every element in a contiguous range, as well as querying the sum over any contiguous range, both in O(log n).

Internally, two classic Fenwick trees (B1, B2) are kept so that the prefix sum can be recovered as

\[ P(i) = (i+1)\,\text{B1.prefix}(i) - \text{B2.prefix}(i) \]

This class is restricted to signed arithmetic types (it uses multiplication, subtraction, and negative deltas directly).

Template Parameters

T	signed arithmetic element type.

Complexity

Operation	Time
Construction	O(n)
update (range)	O(log n)
prefix	O(log n)
query	O(log n)
get / set	O(log n)
Space	O(n)

Example: Range_Fenwick_Tree<int> ft(8);

ft.update(1, 4, 3); // a[1..4] += 3

ft.update(2, 6, 5); // a[2..6] += 5

int s = ft.query(0, 7); // sum of entire array

int v = ft.get(3); // value at index 3 = 3 + 5 = 8

Aleph::DynList::get
T get()
Definition htlist.H:1637

Aleph::Range_Fenwick_Tree
Fenwick tree supporting range updates and range queries.
Definition tpl_fenwick_tree.H:498

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

See also: Gen_Fenwick_Tree Point-update / range-query variant.; Fenwick_Tree Arithmetic specialisation with find_kth.

Definition at line 497 of file tpl_fenwick_tree.H.

Member Typedef Documentation

◆ Item_Type

template<FenwickArithmetic T>

using Aleph::Range_Fenwick_Tree< T >::Item_Type = T

Definition at line 524 of file tpl_fenwick_tree.H.

Constructor & Destructor Documentation

◆ Range_Fenwick_Tree() [1/5]

template<FenwickArithmetic T>

Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree ( const size_t num )

inline

Construct a tree with num elements, all zero.

Definition at line 527 of file tpl_fenwick_tree.H.

◆ Range_Fenwick_Tree() [2/5]

template<FenwickArithmetic T>

Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree ( std::initializer_list< T > il )

inline

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

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

ft.update(0, 4, 10); // add 10 to all elements

Definition at line 541 of file tpl_fenwick_tree.H.

References StlAlephIterator< SetName >::begin(), Aleph::Range_Fenwick_Tree< T >::build_from_diffs(), Aleph::Array< T >::create(), Aleph::maps(), and Aleph::Range_Fenwick_Tree< T >::n.

◆ Range_Fenwick_Tree() [3/5]

template<FenwickArithmetic T>

Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree ( const Array< T > & values )

inline

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

Parameters

values source array with the initial element values.

Definition at line 563 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::build_from_diffs(), Aleph::Array< T >::create(), Aleph::Range_Fenwick_Tree< T >::n, and Aleph::Range_Fenwick_Tree< T >::values().

◆ Range_Fenwick_Tree() [4/5]

template<FenwickArithmetic T>

Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree ( const Range_Fenwick_Tree< T > & )

default

◆ Range_Fenwick_Tree() [5/5]

template<FenwickArithmetic T>

Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree ( Range_Fenwick_Tree< T > && )

defaultnoexcept

Member Function Documentation

◆ build_from_diffs()

template<FenwickArithmetic T>

void Aleph::Range_Fenwick_Tree< T >::build_from_diffs ( const Array< T > & d )

inlineprivate

Rebuild b1 and b2 from a difference array stored in d.

Definition at line 510 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::b1, Aleph::Range_Fenwick_Tree< T >::b2, Aleph::Array< T >::create(), Aleph::maps(), and Aleph::Range_Fenwick_Tree< T >::n.

Referenced by Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree(), and Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree().

◆ get()

template<FenwickArithmetic T>

T Aleph::Range_Fenwick_Tree< T >::get ( const size_t i ) const

inline

Retrieve the logical value a[i].

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

Definition at line 654 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::query().

Referenced by Aleph::Range_Fenwick_Tree< T >::set(), TEST(), and Aleph::Range_Fenwick_Tree< T >::values().

◆ is_empty()

template<FenwickArithmetic T>

constexpr bool Aleph::Range_Fenwick_Tree< T >::is_empty ( ) const

inlineconstexprnoexcept

True if the tree contains no elements.

Definition at line 672 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::n.

◆ operator=() [1/2]

template<FenwickArithmetic T>

Range_Fenwick_Tree & Aleph::Range_Fenwick_Tree< T >::operator= ( const Range_Fenwick_Tree< T > & )

default

◆ operator=() [2/2]

template<FenwickArithmetic T>

Range_Fenwick_Tree & Aleph::Range_Fenwick_Tree< T >::operator= ( Range_Fenwick_Tree< T > && )

defaultnoexcept

◆ point_update()

template<FenwickArithmetic T>

void Aleph::Range_Fenwick_Tree< T >::point_update	(	const size_t	i,
		const T &	delta
	)

inline

Point update: add delta to a[i].

Convenience shorthand for update(i, i, delta).

Definition at line 614 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::update().

Referenced by Aleph::Range_Fenwick_Tree< T >::set().

◆ prefix()

template<FenwickArithmetic T>

T Aleph::Range_Fenwick_Tree< T >::prefix ( const size_t i ) const

inline

Prefix query: sum of a[0..i].

Parameters

i	0-based index.

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

Exceptions

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

Definition at line 625 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if, Aleph::Range_Fenwick_Tree< T >::n, and Aleph::Range_Fenwick_Tree< T >::prefix_sum().

Referenced by TEST().

◆ prefix_sum()

template<FenwickArithmetic T>

T Aleph::Range_Fenwick_Tree< T >::prefix_sum ( size_t i ) const

inlineprivate

Internal: prefix sum P(i) = (i+1)*B1.prefix(i) - B2.prefix(i)

Definition at line 504 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::b1, and Aleph::Range_Fenwick_Tree< T >::b2.

Referenced by Aleph::Range_Fenwick_Tree< T >::prefix(), and Aleph::Range_Fenwick_Tree< T >::query().

◆ query()

template<FenwickArithmetic T>

T Aleph::Range_Fenwick_Tree< T >::query	(	const size_t	l,
		const size_t	r
	)		const

inline

Range query: sum of a[l..r].

Parameters

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

Returns: accumulated sum over [l, r].

Exceptions

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

Definition at line 640 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if, l, Aleph::Range_Fenwick_Tree< T >::n, and Aleph::Range_Fenwick_Tree< T >::prefix_sum().

Referenced by Aleph::Range_Fenwick_Tree< T >::get(), and TEST().

◆ set()

template<FenwickArithmetic T>

void Aleph::Range_Fenwick_Tree< T >::set	(	const size_t	i,
		const T &	value
	)

inline

Set a[i] = value.

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

Definition at line 663 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::get(), and Aleph::Range_Fenwick_Tree< T >::point_update().

◆ size()

template<FenwickArithmetic T>

constexpr size_t Aleph::Range_Fenwick_Tree< T >::size ( ) const

inlineconstexprnoexcept

Number of logical elements.

Definition at line 669 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::n.

Referenced by TEST().

◆ swap()

template<FenwickArithmetic T>

void Aleph::Range_Fenwick_Tree< T >::swap ( Range_Fenwick_Tree< T > & other )

inlinenoexcept

Swap this tree with other in O(1).

Definition at line 687 of file tpl_fenwick_tree.H.

References Aleph::Range_Fenwick_Tree< T >::b1, Aleph::Range_Fenwick_Tree< T >::b2, Aleph::maps(), and Aleph::Range_Fenwick_Tree< T >::n.

Referenced by TEST().

◆ update()

template<FenwickArithmetic T>

void Aleph::Range_Fenwick_Tree< T >::update	(	size_t	l,
		const size_t	r,
		const T &	delta
	)

inline

Range update: add delta to every a[i] with l <= i <= r.

Parameters

l	0-based left index (inclusive).
r	0-based right index (inclusive).
delta	value to add to each element in `[l, r]`.

Exceptions

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

Definition at line 592 of file tpl_fenwick_tree.H.

References ah_out_of_range_error_if, Aleph::Range_Fenwick_Tree< T >::b1, Aleph::Range_Fenwick_Tree< T >::b2, l, Aleph::maps(), and Aleph::Range_Fenwick_Tree< T >::n.

Referenced by Aleph::Range_Fenwick_Tree< T >::point_update().

◆ values()

template<FenwickArithmetic T>

Array< T > Aleph::Range_Fenwick_Tree< T >::values ( ) const

inline

Reconstruct all original values into an Array.

O(n log n).

Definition at line 678 of file tpl_fenwick_tree.H.

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

Referenced by Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree().

Member Data Documentation

◆ b1

template<FenwickArithmetic T>

Gen_Fenwick_Tree<T> Aleph::Range_Fenwick_Tree< T >::b1

private

Definition at line 499 of file tpl_fenwick_tree.H.

Referenced by Aleph::Range_Fenwick_Tree< T >::build_from_diffs(), Aleph::Range_Fenwick_Tree< T >::prefix_sum(), Aleph::Range_Fenwick_Tree< T >::swap(), and Aleph::Range_Fenwick_Tree< T >::update().

◆ b2

template<FenwickArithmetic T>

Gen_Fenwick_Tree<T> Aleph::Range_Fenwick_Tree< T >::b2

private

Definition at line 500 of file tpl_fenwick_tree.H.

Referenced by Aleph::Range_Fenwick_Tree< T >::build_from_diffs(), Aleph::Range_Fenwick_Tree< T >::prefix_sum(), Aleph::Range_Fenwick_Tree< T >::swap(), and Aleph::Range_Fenwick_Tree< T >::update().

◆ n

template<FenwickArithmetic T>

size_t Aleph::Range_Fenwick_Tree< T >::n = 0

private

Definition at line 501 of file tpl_fenwick_tree.H.

Referenced by Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree(), Aleph::Range_Fenwick_Tree< T >::Range_Fenwick_Tree(), Aleph::Range_Fenwick_Tree< T >::build_from_diffs(), Aleph::Range_Fenwick_Tree< T >::is_empty(), Aleph::Range_Fenwick_Tree< T >::prefix(), Aleph::Range_Fenwick_Tree< T >::query(), Aleph::Range_Fenwick_Tree< T >::size(), Aleph::Range_Fenwick_Tree< T >::swap(), Aleph::Range_Fenwick_Tree< T >::update(), and Aleph::Range_Fenwick_Tree< T >::values().

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

tpl_fenwick_tree.H

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Item_Type

Constructor & Destructor Documentation

◆ Range_Fenwick_Tree() [1/5]

◆ Range_Fenwick_Tree() [2/5]

◆ Range_Fenwick_Tree() [3/5]

◆ Range_Fenwick_Tree() [4/5]

◆ Range_Fenwick_Tree() [5/5]

Member Function Documentation

◆ build_from_diffs()

◆ get()

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ point_update()

◆ prefix()

◆ prefix_sum()

◆ query()

◆ set()

◆ size()

◆ swap()

◆ update()

◆ values()

Member Data Documentation

◆ b1

◆ b2

◆ n