Ji Driver's Segment Tree (Segment Tree Beats). More...

#include <tpl_segment_tree.H>

Collaboration diagram for Aleph::Segment_Tree_Beats< T >:

Classes
struct	Node

Public Types
using	Item_Type = T

Public Member Functions
	Segment_Tree_Beats (const size_t num, const T &init_val=T())
	Construct with `num` elements, all equal to `init_val`.

	Segment_Tree_Beats (std::initializer_list< T > il)
	Construct from an initializer list.

	Segment_Tree_Beats (const Array< T > &values)
	Construct from an Array<T>.

	Segment_Tree_Beats (const std::vector< T > &values)
	Construct from a std::vector<T>.

	Segment_Tree_Beats (const DynList< T > &values)
	Construct from a DynList<T>.

	Segment_Tree_Beats (const Segment_Tree_Beats &)=default

	Segment_Tree_Beats (Segment_Tree_Beats &&) noexcept(std::is_nothrow_move_constructible_v< Array< Node > >)=default

Segment_Tree_Beats &	operator= (const Segment_Tree_Beats &)=default

Segment_Tree_Beats &	operator= (Segment_Tree_Beats &&) noexcept(std::is_nothrow_move_assignable_v< Array< Node > >)=default

void	chmin (const size_t l, const size_t r, const T &v)
	Range chmin: for each `i` in `[l, r]`, set `a[i] = min(a[i], v)`.

void	chmax (const size_t l, const size_t r, const T &v)
	Range chmax: for each `i` in `[l, r]`, set `a[i] = max(a[i], v)`.

T	query_sum (const size_t l, const size_t r) const
	Range sum query over `[l, r]`.

T	query_max (const size_t l, const size_t r) const
	Range max query over `[l, r]`.

T	query_min (const size_t l, const size_t r) const
	Range min query over `[l, r]`.

T	get (const size_t i) const
	Retrieve the value at position `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 values into an Array.

void	swap (Segment_Tree_Beats &other) noexcept
	Swap this tree with `other` in O(1).

Private Member Functions
void	init_leaf (size_t node, const T &val)

void	pull_up (size_t node) const

void	push_chmin_to_child (size_t child, T v) const

void	push_chmax_to_child (size_t child, T v) const

void	push_down (size_t node) const

void	build (size_t node, size_t start, size_t end)

void	chmin_impl (size_t node, const size_t start, const size_t end, const size_t l, const size_t r, T v)

void	chmax_impl (size_t node, const size_t start, const size_t end, const size_t l, const size_t r, T v)

T	query_sum_impl (size_t node, const size_t start, const size_t end, const size_t l, const size_t r) const

T	query_max_impl (size_t node, const size_t start, const size_t end, const size_t l, const size_t r) const

T	query_min_impl (size_t node, const size_t start, const size_t end, const size_t l, const size_t r) const

template<class Getter >
void	fill_and_build (Getter getter)

template<class Getter >
void	fill_leaves_recursive (const size_t node, size_t start, size_t end, Getter &getter)

void	init_all_nodes ()

Private Attributes
Array< Node >	tree

size_t	n = 0

Static Private Attributes
static constexpr T	INF = std::numeric_limits<T>::max()

static constexpr T	NEG_INF = std::numeric_limits<T>::lowest()

Detailed Description

template<typename T>
requires std::is_arithmetic_v<T>
class Aleph::Segment_Tree_Beats< T >

Ji Driver's Segment Tree (Segment Tree Beats).

Supports range chmin(l, r, v) and chmax(l, r, v) operations together with range sum, min, and max queries.

Each node maintains: max, second_max, count_max, min, second_min, count_min, sum. The push-down uses break/tag conditions for amortised O(n log^2 n) total complexity.

When to use: Use this structure when you need range clamping operations (chmin/chmax) in addition to sum/min/max queries. For simpler update patterns, prefer Gen_Lazy_Segment_Tree.

Template Parameters

T	a signed arithmetic type.

Example: Segment_Tree_Beats<int> st = {5, 2, 4, 7, 1};

st.chmin(0, 4, 4); // clamp all to <= 4

// array becomes {4, 2, 4, 4, 1}

st.query_sum(0, 4); // 15

st.query_max(0, 4); // 4

Aleph::Segment_Tree_Beats
Ji Driver's Segment Tree (Segment Tree Beats).
Definition tpl_segment_tree.H:1317

Aleph::Segment_Tree_Beats::query_sum
T query_sum(const size_t l, const size_t r) const
Range sum query over [l, r].
Definition tpl_segment_tree.H:1697

Aleph::Segment_Tree_Beats::query_max
T query_max(const size_t l, const size_t r) const
Range max query over [l, r].
Definition tpl_segment_tree.H:1711

Aleph::Segment_Tree_Beats::chmin
void chmin(const size_t l, const size_t r, const T &v)
Range chmin: for each i in [l, r], set a[i] = min(a[i], v).
Definition tpl_segment_tree.H:1669

Definition at line 1316 of file tpl_segment_tree.H.

Member Typedef Documentation

◆ Item_Type

template<typename T >

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

Definition at line 1577 of file tpl_segment_tree.H.

Constructor & Destructor Documentation

◆ Segment_Tree_Beats() [1/7]

template<typename T >

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

inline

Construct with num elements, all equal to init_val.

Parameters

num	number of elements to allocate in the tree.
init_val	initial value assigned to every leaf.

Exceptions

std::bad_alloc if internal storage allocation fails.

Definition at line 1585 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::fill_and_build(), Aleph::Segment_Tree_Beats< T >::init_all_nodes(), and Aleph::Segment_Tree_Beats< T >::n.

◆ Segment_Tree_Beats() [2/7]

template<typename T >

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

inline

Construct from an initializer list.

Parameters

il	source initializer list with the initial values.

Exceptions

std::bad_alloc if internal storage allocation fails.

Definition at line 1598 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::fill_and_build(), Aleph::Segment_Tree_Beats< T >::init_all_nodes(), and Aleph::Segment_Tree_Beats< T >::n.

◆ Segment_Tree_Beats() [3/7]

template<typename T >

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

inline

Construct from an Array<T>.

Parameters

values source array with the initial values.

Exceptions

std::bad_alloc if internal storage allocation fails.

Definition at line 1615 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::fill_and_build(), Aleph::Segment_Tree_Beats< T >::init_all_nodes(), Aleph::Segment_Tree_Beats< T >::n, and Aleph::Segment_Tree_Beats< T >::values().

◆ Segment_Tree_Beats() [4/7]

template<typename T >

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

inline

Construct from a std::vector<T>.

Parameters

values source vector with the initial values.

Exceptions

std::bad_alloc if internal storage allocation fails.

Definition at line 1629 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::fill_and_build(), Aleph::Segment_Tree_Beats< T >::init_all_nodes(), Aleph::Segment_Tree_Beats< T >::n, and Aleph::Segment_Tree_Beats< T >::values().

◆ Segment_Tree_Beats() [5/7]

template<typename T >

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

inline

Construct from a DynList<T>.

Parameters

values source list with the initial values.

Exceptions

std::bad_alloc if internal storage allocation fails.

Definition at line 1643 of file tpl_segment_tree.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::fill_and_build(), Aleph::Segment_Tree_Beats< T >::init_all_nodes(), Aleph::Segment_Tree_Beats< T >::n, and Aleph::Segment_Tree_Beats< T >::values().

◆ Segment_Tree_Beats() [6/7]

template<typename T >

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

default

◆ Segment_Tree_Beats() [7/7]

template<typename T >

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

defaultnoexcept

Member Function Documentation

◆ build()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::build	(	size_t	node,
		size_t	start,
		size_t	end
	)

inlineprivate

Definition at line 1452 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::build(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::pull_up().

Referenced by Aleph::Segment_Tree_Beats< T >::build(), and Aleph::Segment_Tree_Beats< T >::fill_and_build().

◆ chmax()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::chmax	(	const size_t	l,
		const size_t	r,
		const T &	v
	)

inline

Range chmax: for each i in [l, r], set a[i] = max(a[i], v).

Exceptions

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

Definition at line 1683 of file tpl_segment_tree.H.

References ah_out_of_range_error_if, Aleph::Segment_Tree_Beats< T >::chmax_impl(), l, Aleph::Segment_Tree_Beats< T >::n, and r.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ chmax_impl()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::chmax_impl	(	size_t	node,
		const size_t	start,
		const size_t	end,
		const size_t	l,
		const size_t	r,
		T	v
	)

inlineprivate

Definition at line 1482 of file tpl_segment_tree.H.

References Aleph::and, Aleph::Segment_Tree_Beats< T >::chmax_impl(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::Segment_Tree_Beats< T >::pull_up(), Aleph::Segment_Tree_Beats< T >::push_chmax_to_child(), Aleph::Segment_Tree_Beats< T >::push_down(), r, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::chmax(), and Aleph::Segment_Tree_Beats< T >::chmax_impl().

◆ chmin()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::chmin	(	const size_t	l,
		const size_t	r,
		const T &	v
	)

inline

Range chmin: for each i in [l, r], set a[i] = min(a[i], v).

Exceptions

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

Definition at line 1669 of file tpl_segment_tree.H.

References ah_out_of_range_error_if, Aleph::Segment_Tree_Beats< T >::chmin_impl(), l, Aleph::Segment_Tree_Beats< T >::n, and r.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ chmin_impl()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::chmin_impl	(	size_t	node,
		const size_t	start,
		const size_t	end,
		const size_t	l,
		const size_t	r,
		T	v
	)

inlineprivate

Definition at line 1463 of file tpl_segment_tree.H.

References Aleph::and, Aleph::Segment_Tree_Beats< T >::chmin_impl(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::Segment_Tree_Beats< T >::pull_up(), Aleph::Segment_Tree_Beats< T >::push_chmin_to_child(), Aleph::Segment_Tree_Beats< T >::push_down(), r, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::chmin(), and Aleph::Segment_Tree_Beats< T >::chmin_impl().

◆ fill_and_build()

template<typename T >

template<class Getter >

void Aleph::Segment_Tree_Beats< T >::fill_and_build ( Getter getter )

inlineprivate

Definition at line 1547 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::build(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::fill_leaves_recursive(), and Aleph::Segment_Tree_Beats< T >::n.

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

◆ fill_leaves_recursive()

template<typename T >

template<class Getter >

void Aleph::Segment_Tree_Beats< T >::fill_leaves_recursive	(	const size_t	node,
		size_t	start,
		size_t	end,
		Getter &	getter
	)

inlineprivate

Definition at line 1554 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::fill_leaves_recursive(), and Aleph::Segment_Tree_Beats< T >::init_leaf().

Referenced by Aleph::Segment_Tree_Beats< T >::fill_and_build(), and Aleph::Segment_Tree_Beats< T >::fill_leaves_recursive().

◆ get()

template<typename T >

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

inline

Retrieve the value at position i.

O(log n).

Definition at line 1736 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::query_sum().

Referenced by scenario_3_balanceo_servidores(), TEST(), TEST(), and Aleph::Segment_Tree_Beats< T >::values().

◆ init_all_nodes()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::init_all_nodes ( )

inlineprivate

Definition at line 1568 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::INF, Aleph::Segment_Tree_Beats< T >::NEG_INF, and Aleph::Segment_Tree_Beats< T >::tree.

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

◆ init_leaf()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::init_leaf	(	size_t	node,
		const T &	val
	)

inlineprivate

Definition at line 1331 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::INF, Aleph::Segment_Tree_Beats< T >::NEG_INF, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::fill_leaves_recursive().

◆ is_empty()

template<typename T >

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

inlineconstexprnoexcept

True if the tree contains no elements.

Definition at line 1745 of file tpl_segment_tree.H.

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

Referenced by TEST().

◆ operator=() [1/2]

template<typename T >

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

default

◆ operator=() [2/2]

template<typename T >

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

defaultnoexcept

◆ pull_up()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::pull_up ( size_t node ) const

inlineprivate

Definition at line 1337 of file tpl_segment_tree.H.

References Aleph::Segment_Tree_Beats< T >::INF, l, Aleph::Segment_Tree_Beats< T >::NEG_INF, r, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::build(), Aleph::Segment_Tree_Beats< T >::chmax_impl(), and Aleph::Segment_Tree_Beats< T >::chmin_impl().

◆ push_chmax_to_child()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::push_chmax_to_child	(	size_t	child,
		T	v
	)		const

inlineprivate

Definition at line 1410 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::chmax_impl(), and Aleph::Segment_Tree_Beats< T >::push_down().

◆ push_chmin_to_child()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::push_chmin_to_child	(	size_t	child,
		T	v
	)		const

inlineprivate

Definition at line 1388 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::chmin_impl(), and Aleph::Segment_Tree_Beats< T >::push_down().

◆ push_down()

template<typename T >

void Aleph::Segment_Tree_Beats< T >::push_down ( size_t node ) const

inlineprivate

Definition at line 1431 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::INF, Aleph::Segment_Tree_Beats< T >::NEG_INF, Aleph::Segment_Tree_Beats< T >::push_chmax_to_child(), Aleph::Segment_Tree_Beats< T >::push_chmin_to_child(), and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::chmax_impl(), Aleph::Segment_Tree_Beats< T >::chmin_impl(), Aleph::Segment_Tree_Beats< T >::query_max_impl(), Aleph::Segment_Tree_Beats< T >::query_min_impl(), and Aleph::Segment_Tree_Beats< T >::query_sum_impl().

◆ query_max()

template<typename T >

T Aleph::Segment_Tree_Beats< T >::query_max	(	const size_t	l,
		const size_t	r
	)		const

inline

Range max query over [l, r].

Exceptions

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

Definition at line 1711 of file tpl_segment_tree.H.

References ah_out_of_range_error_if, l, Aleph::Segment_Tree_Beats< T >::n, Aleph::Segment_Tree_Beats< T >::query_max_impl(), and r.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ query_max_impl()

template<typename T >

T Aleph::Segment_Tree_Beats< T >::query_max_impl	(	size_t	node,
		const size_t	start,
		const size_t	end,
		const size_t	l,
		const size_t	r
	)		const

inlineprivate

Definition at line 1516 of file tpl_segment_tree.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), l, Aleph::Segment_Tree_Beats< T >::NEG_INF, Aleph::Segment_Tree_Beats< T >::push_down(), Aleph::Segment_Tree_Beats< T >::query_max_impl(), r, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::query_max(), and Aleph::Segment_Tree_Beats< T >::query_max_impl().

◆ query_min()

template<typename T >

T Aleph::Segment_Tree_Beats< T >::query_min	(	const size_t	l,
		const size_t	r
	)		const

inline

Range min query over [l, r].

Exceptions

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

Definition at line 1725 of file tpl_segment_tree.H.

References ah_out_of_range_error_if, l, Aleph::Segment_Tree_Beats< T >::n, Aleph::Segment_Tree_Beats< T >::query_min_impl(), and r.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ query_min_impl()

template<typename T >

T Aleph::Segment_Tree_Beats< T >::query_min_impl	(	size_t	node,
		const size_t	start,
		const size_t	end,
		const size_t	l,
		const size_t	r
	)		const

inlineprivate

Definition at line 1531 of file tpl_segment_tree.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::INF, l, Aleph::Segment_Tree_Beats< T >::push_down(), Aleph::Segment_Tree_Beats< T >::query_min_impl(), r, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::query_min(), and Aleph::Segment_Tree_Beats< T >::query_min_impl().

◆ query_sum()

template<typename T >

T Aleph::Segment_Tree_Beats< T >::query_sum	(	const size_t	l,
		const size_t	r
	)		const

inline

Range sum query over [l, r].

Exceptions

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

Definition at line 1697 of file tpl_segment_tree.H.

References ah_out_of_range_error_if, l, Aleph::Segment_Tree_Beats< T >::n, Aleph::Segment_Tree_Beats< T >::query_sum_impl(), and r.

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

◆ query_sum_impl()

template<typename T >

T Aleph::Segment_Tree_Beats< T >::query_sum_impl	(	size_t	node,
		const size_t	start,
		const size_t	end,
		const size_t	l,
		const size_t	r
	)		const

inlineprivate

Definition at line 1501 of file tpl_segment_tree.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), l, Aleph::Segment_Tree_Beats< T >::push_down(), Aleph::Segment_Tree_Beats< T >::query_sum_impl(), r, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by Aleph::Segment_Tree_Beats< T >::query_sum(), and Aleph::Segment_Tree_Beats< T >::query_sum_impl().

◆ size()

template<typename T >

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

inlineconstexprnoexcept

Number of logical elements.

Definition at line 1742 of file tpl_segment_tree.H.

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

Referenced by TEST().

◆ swap()

template<typename T >

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

inlinenoexcept

Swap this tree with other in O(1).

Definition at line 1757 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::n, and Aleph::Segment_Tree_Beats< T >::tree.

Referenced by TEST().

◆ values()

template<typename T >

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

inline

Reconstruct all values into an Array.

O(n log n).

Definition at line 1748 of file tpl_segment_tree.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment_Tree_Beats< T >::get(), and Aleph::Segment_Tree_Beats< T >::n.

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

Member Data Documentation

◆ INF

template<typename T >

constexpr T Aleph::Segment_Tree_Beats< T >::INF = std::numeric_limits<T>::max()

staticconstexprprivate

Definition at line 1328 of file tpl_segment_tree.H.

Referenced by Aleph::Segment_Tree_Beats< T >::init_all_nodes(), Aleph::Segment_Tree_Beats< T >::init_leaf(), Aleph::Segment_Tree_Beats< T >::pull_up(), Aleph::Segment_Tree_Beats< T >::push_down(), and Aleph::Segment_Tree_Beats< T >::query_min_impl().

◆ n

template<typename T >

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

private

Definition at line 1326 of file tpl_segment_tree.H.

◆ NEG_INF

template<typename T >

constexpr T Aleph::Segment_Tree_Beats< T >::NEG_INF = std::numeric_limits<T>::lowest()

staticconstexprprivate

Definition at line 1329 of file tpl_segment_tree.H.

Referenced by Aleph::Segment_Tree_Beats< T >::init_all_nodes(), Aleph::Segment_Tree_Beats< T >::init_leaf(), Aleph::Segment_Tree_Beats< T >::pull_up(), Aleph::Segment_Tree_Beats< T >::push_down(), and Aleph::Segment_Tree_Beats< T >::query_max_impl().

◆ tree

template<typename T >

Array<Node> Aleph::Segment_Tree_Beats< T >::tree

mutableprivate

Definition at line 1325 of file tpl_segment_tree.H.

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

tpl_segment_tree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Item_Type

Constructor & Destructor Documentation

◆ Segment_Tree_Beats() [1/7]

◆ Segment_Tree_Beats() [2/7]

◆ Segment_Tree_Beats() [3/7]

◆ Segment_Tree_Beats() [4/7]

◆ Segment_Tree_Beats() [5/7]

◆ Segment_Tree_Beats() [6/7]

◆ Segment_Tree_Beats() [7/7]

Member Function Documentation

◆ build()

◆ chmax()

◆ chmax_impl()

◆ chmin()

◆ chmin_impl()

◆ fill_and_build()

◆ fill_leaves_recursive()

◆ get()

◆ init_all_nodes()

◆ init_leaf()

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pull_up()

◆ push_chmax_to_child()

◆ push_chmin_to_child()

◆ push_down()

◆ query_max()

◆ query_max_impl()

◆ query_min()

◆ query_min_impl()

◆ query_sum()

◆ query_sum_impl()

◆ size()

◆ swap()

◆ values()

Member Data Documentation

◆ INF

◆ n

◆ NEG_INF

◆ tree