Aleph::Max_Segment_Tree< T > Struct Template Reference

Max Segment Tree for range maximum queries with point updates. More...

#include <tpl_segment_tree.H>

Inheritance diagram for Aleph::Max_Segment_Tree< T >:

Collaboration diagram for Aleph::Max_Segment_Tree< T >:

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

Public Member Functions
	Max_Segment_Tree (const size_t num, const T &init_val=std::numeric_limits< T >::lowest())
	Construct with num elements, all equal to init_val.
	Max_Segment_Tree (std::initializer_list< T > il)
	Construct from an initializer list.
	Max_Segment_Tree (const Array< T > &values)
	Construct from an Array<T>.
	Max_Segment_Tree (const std::vector< T > &values)
	Construct from a std::vector<T>.
	Max_Segment_Tree (const DynList< T > &values)
	Construct from a DynList<T>.
Public Member Functions inherited from Aleph::Gen_Segment_Tree< T, Max_Op< T > >
	Gen_Segment_Tree (const size_t num, const T &init_val, const T &id, Max_Op< T > oper=Max_Op< T >())
	Construct a segment tree with num elements, all equal to init_val.
	Gen_Segment_Tree (std::initializer_list< T > il, const T &id, Max_Op< T > oper=Max_Op< T >())
	Construct from an initializer list.
	Gen_Segment_Tree (const Array< T > &values, const T &id, Max_Op< T > oper=Max_Op< T >())
	Construct from an Array<T>.
	Gen_Segment_Tree (const std::vector< T > &values, const T &id, Max_Op< T > oper=Max_Op< T >())
	Construct from a std::vector<T>.
	Gen_Segment_Tree (const DynList< T > &values, const T &id, Max_Op< T > oper=Max_Op< 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< Max_Op< 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< Max_Op< 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< Max_Op< T > & >(), std::declval< Max_Op< T > & >())))
	Swap this tree with other in O(1).

Detailed Description

template<std::totally_ordered T>
struct Aleph::Max_Segment_Tree< T >

Max Segment Tree for range maximum queries with point updates.

Convenient specialisation of Gen_Segment_Tree using Max_Op<T> with identity numeric_limits<T>::lowest().

Template Parameters

T	a totally ordered type with numeric_limits support.

Note

This structure supports point updates and range maximum queries. For static range max queries with O(1) queries, prefer Max_Sparse_Table.

Example

Max_Segment_Tree<int> st = {5, 2, 4, 7, 1};
assert(st.query(0, 3) == 7);  // max(5, 2, 4, 7)
st.set(3, 0);
assert(st.query(0, 3) == 5);  // max(5, 2, 4, 0)

Definition at line 611 of file tpl_segment_tree.H.

Member Typedef Documentation

Base

template<std::totally_ordered T>

using Aleph::Max_Segment_Tree< T >::Base = Gen_Segment_Tree<T, Max_Op<T> >

Definition at line 614 of file tpl_segment_tree.H.

Constructor & Destructor Documentation

Max_Segment_Tree() [1/5]

template<std::totally_ordered T>

Aleph::Max_Segment_Tree< T >::Max_Segment_Tree ( const size_t  num, const T &  init_val = std::numeric_limits<T>::lowest()  )

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 622 of file tpl_segment_tree.H.

Max_Segment_Tree() [2/5]

template<std::totally_ordered T>

Aleph::Max_Segment_Tree< T >::Max_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 632 of file tpl_segment_tree.H.

Max_Segment_Tree() [3/5]

template<std::totally_ordered T>

Aleph::Max_Segment_Tree< T >::Max_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 641 of file tpl_segment_tree.H.

Max_Segment_Tree() [4/5]

template<std::totally_ordered T>

Aleph::Max_Segment_Tree< T >::Max_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 650 of file tpl_segment_tree.H.

Max_Segment_Tree() [5/5]

template<std::totally_ordered T>

Aleph::Max_Segment_Tree< T >::Max_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 659 of file tpl_segment_tree.H.

---

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

• tpl_segment_tree.H