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

#include <tpl_disjoint_sparse_table.H>

Inheritance diagram for Aleph::Product_Disjoint_Sparse_Table< T >:

Collaboration diagram for Aleph::Product_Disjoint_Sparse_Table< T >:

Public Types
using	Base = Gen_Disjoint_Sparse_Table< T, Aleph::multiplies< T > >

Public Types inherited from Aleph::Gen_Disjoint_Sparse_Table< T, Aleph::multiplies< 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::multiplies< T > >
	Gen_Disjoint_Sparse_Table (const size_t num, const T &init_val, Aleph::multiplies< T > oper=Aleph::multiplies< T >())
	Construct a disjoint sparse table with `num` elements, all equal to `init_val`.

	Gen_Disjoint_Sparse_Table (std::initializer_list< T > il, Aleph::multiplies< T > oper=Aleph::multiplies< T >())
	Construct from an initializer list in O(n log n) time.

	Gen_Disjoint_Sparse_Table (const Array< T > &values, Aleph::multiplies< T > oper=Aleph::multiplies< T >())
	Construct from an Array<T> in O(n log n) time.

	Gen_Disjoint_Sparse_Table (const std::vector< T > &values, Aleph::multiplies< T > oper=Aleph::multiplies< T >())
	Construct from a std::vector<T> in O(n log n) time.

	Gen_Disjoint_Sparse_Table (const DynList< T > &values, Aleph::multiplies< T > oper=Aleph::multiplies< 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).