Aleph::Sum_Segment_Tree< T > Struct Template Reference

Sum Segment Tree for range sum queries with point updates. More...

#include <tpl_segment_tree.H>

Inheritance diagram for Aleph::Sum_Segment_Tree< T >:

Collaboration diagram for Aleph::Sum_Segment_Tree< T >:

Public Types
using	Base = Gen_Segment_Tree< T, Aleph::plus< T > >
Public Types inherited from Aleph::Gen_Segment_Tree< T, Aleph::plus< T > >
using	Item_Type = T

Public Member Functions
	Sum_Segment_Tree (const size_t num, const T &init_val=T())
	Construct with num elements, all equal to init_val.
	Sum_Segment_Tree (std::initializer_list< T > il)
	Construct from an initializer list.
	Sum_Segment_Tree (const Array< T > &values)
	Construct from an Array<T>.
	Sum_Segment_Tree (const std::vector< T > &values)
	Construct from a std::vector<T>.
	Sum_Segment_Tree (const DynList< T > &values)
	Construct from a DynList<T>.
Public Member Functions inherited from Aleph::Gen_Segment_Tree< T, Aleph::plus< T > >
	Gen_Segment_Tree (const size_t num, const T &init_val, const T &id, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct a segment tree with num elements, all equal to init_val.
	Gen_Segment_Tree (std::initializer_list< T > il, const T &id, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from an initializer list.
	Gen_Segment_Tree (const Array< T > &values, const T &id, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from an Array<T>.
	Gen_Segment_Tree (const std::vector< T > &values, const T &id, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from a std::vector<T>.
	Gen_Segment_Tree (const DynList< T > &values, const T &id, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from a DynList<T>.
	Gen_Segment_Tree (const Gen_Segment_Tree &)=default
	Gen_Segment_Tree (Gen_Segment_Tree &&) noexcept(std::is_nothrow_move_constructible_v< Array< T > > and std::is_nothrow_move_constructible_v< Aleph::plus< T > >)=default
Gen_Segment_Tree &	operator= (const Gen_Segment_Tree &)=default
Gen_Segment_Tree &	operator= (Gen_Segment_Tree &&) noexcept(std::is_nothrow_move_assignable_v< Array< T > > and std::is_nothrow_move_assignable_v< Aleph::plus< T > >)=default
void	update (const size_t i, const T &delta)
	Point update: a[i] = Op(a[i], delta).
void	set (const size_t i, const T &val)
	Set a[i] = val.
T	query (const size_t l, const size_t r) const
	Range query over [l, r].
T	get (const size_t i) const
	Retrieve the value a[i].
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_Segment_Tree &other) noexcept(noexcept(std::swap(std::declval< T & >(), std::declval< T & >())) and noexcept(std::swap(std::declval< Aleph::plus< T > & >(), std::declval< Aleph::plus< T > & >())))
	Swap this tree with other in O(1).

Detailed Description

template<typename T>
struct Aleph::Sum_Segment_Tree< T >

Sum Segment Tree for range sum queries with point updates.

Convenient specialisation of Gen_Segment_Tree using plus<T> with identity T() (zero for arithmetic types).

Template Parameters

T	an arithmetic type.

Example

Sum_Segment_Tree<int> st = {3, 1, 4, 1, 5};
assert(st.query(0, 4) == 14);
st.update(2, 10);  // a[2] += 10
assert(st.query(0, 4) == 24);

Definition at line 463 of file tpl_segment_tree.H.

Member Typedef Documentation

Base

template<typename T >

using Aleph::Sum_Segment_Tree< T >::Base = Gen_Segment_Tree<T, Aleph::plus<T> >

Definition at line 466 of file tpl_segment_tree.H.

Constructor & Destructor Documentation

Sum_Segment_Tree() [1/5]

template<typename T >

Aleph::Sum_Segment_Tree< T >::Sum_Segment_Tree ( const size_t  num, const T &  init_val = T()  )

inline

Construct with num elements, all equal to init_val.

Parameters

num	number of elements.
init_val	initial value for each element.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 474 of file tpl_segment_tree.H.

Sum_Segment_Tree() [2/5]

template<typename T >

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

inline

Construct from an initializer list.

Parameters

il	source initializer list with the initial element values.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 483 of file tpl_segment_tree.H.

Sum_Segment_Tree() [3/5]

template<typename T >

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

inline

Construct from an Array<T>.

Parameters

values

source array with the initial element values.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 492 of file tpl_segment_tree.H.

Sum_Segment_Tree() [4/5]

template<typename T >

Aleph::Sum_Segment_Tree< T >::Sum_Segment_Tree ( const std::vector< T > &  values )

inline

Construct from a std::vector<T>.

Parameters

values

source vector with the initial element values.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 501 of file tpl_segment_tree.H.

Sum_Segment_Tree() [5/5]

template<typename T >

Aleph::Sum_Segment_Tree< T >::Sum_Segment_Tree ( const DynList< T > &  values )

inline

Construct from a DynList<T>.

Parameters

values

source list with the initial element values.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 510 of file tpl_segment_tree.H.

---

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

• tpl_segment_tree.H