Aleph::Sum_Disjoint_Sparse_Table< T > Struct Template Reference

Disjoint Sparse Table for range sum queries. More...

#include <tpl_disjoint_sparse_table.H>

Inheritance diagram for Aleph::Sum_Disjoint_Sparse_Table< T >:

Collaboration diagram for Aleph::Sum_Disjoint_Sparse_Table< T >:

Public Types
using	Base = Gen_Disjoint_Sparse_Table< T, Aleph::plus< T > >
Public Types inherited from Aleph::Gen_Disjoint_Sparse_Table< T, Aleph::plus< T > >
using	Item_Type = T
	The type of the element stored in the table.

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Disjoint_Sparse_Table< T, Aleph::plus< T > >
	Gen_Disjoint_Sparse_Table (const size_t num, const T &init_val, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct a disjoint sparse table with num elements, all equal to init_val.
	Gen_Disjoint_Sparse_Table (std::initializer_list< T > il, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from an initializer list in O(n log n) time.
	Gen_Disjoint_Sparse_Table (const Array< T > &values, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from an Array<T> in O(n log n) time.
	Gen_Disjoint_Sparse_Table (const std::vector< T > &values, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from a std::vector<T> in O(n log n) time.
	Gen_Disjoint_Sparse_Table (const DynList< T > &values, Aleph::plus< T > oper=Aleph::plus< T >())
	Construct from a DynList<T> in O(n log n) time.
	Gen_Disjoint_Sparse_Table (const Gen_Disjoint_Sparse_Table &)=default
	Gen_Disjoint_Sparse_Table (Gen_Disjoint_Sparse_Table &&) noexcept=default
Gen_Disjoint_Sparse_Table &	operator= (const Gen_Disjoint_Sparse_Table &)=default
Gen_Disjoint_Sparse_Table &	operator= (Gen_Disjoint_Sparse_Table &&) noexcept=default
T	query (const size_t l, const size_t r) const
	Range query over [l, r] in O(1).
T	get (const size_t i) const
	Retrieve the value a[i] in O(1).
constexpr size_t	size () const noexcept
	Number of logical elements.
constexpr bool	is_empty () const noexcept
	True if the table contains no elements.
constexpr size_t	num_levels () const noexcept
	Number of precomputed levels.
Array< T >	values () const
	Reconstruct all original values into an Array.
void	swap (Gen_Disjoint_Sparse_Table &other) noexcept
	Swap this table with other in O(1).

Detailed Description

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

Disjoint Sparse Table for range sum queries.

Convenient specialisation of Gen_Disjoint_Sparse_Table using Aleph::plus<T> for O(1) range sum queries on a static array.

Template Parameters

T	an arithmetic type supporting operator+.

Example

Sum_Disjoint_Sparse_Table<int> st = {3, 1, 4, 1, 5, 9};
assert(st.query(0, 5) == 23);   // 3+1+4+1+5+9
assert(st.query(2, 4) == 10);   // 4+1+5
assert(st.query(3, 3) == 1);    // single element

Definition at line 435 of file tpl_disjoint_sparse_table.H.

Member Typedef Documentation

Base

template<typename T >

using Aleph::Sum_Disjoint_Sparse_Table< T >::Base = Gen_Disjoint_Sparse_Table<T, Aleph::plus<T> >

Definition at line 438 of file tpl_disjoint_sparse_table.H.

---

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

• tpl_disjoint_sparse_table.H