Segment tree over an arbitrary associative binary operation. More...

#include <tpl_segment_tree.H>

Inheritance diagram for Aleph::Gen_Segment_Tree< T, Op >:

Collaboration diagram for Aleph::Gen_Segment_Tree< T, Op >:

Public Types
using	Item_Type = T

Public Member Functions
	Gen_Segment_Tree (const size_t num, const T &init_val, const T &id, Op oper=Op())
	Construct a segment tree with `num` elements, all equal to `init_val`.

	Gen_Segment_Tree (std::initializer_list< T > il, const T &id, Op oper=Op())
	Construct from an initializer list.

	Gen_Segment_Tree (const Array< T > &values, const T &id, Op oper=Op())
	Construct from an Array<T>.

	Gen_Segment_Tree (const std::vector< T > &values, const T &id, Op oper=Op())
	Construct from a std::vector<T>.

	Gen_Segment_Tree (const DynList< T > &values, const T &id, Op oper=Op())
	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< Op >)=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< Op >)=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< Op & >(), std::declval< Op & >())))
	Swap this tree with `other` in O(1).

Private Member Functions
void	build (size_t node, const size_t start, const size_t end)

void	update_impl (size_t node, const size_t start, const size_t end, const size_t idx, const T &delta)

void	set_impl (size_t node, const size_t start, const size_t end, const size_t idx, const T &val)

T	query_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 (size_t node, size_t start, size_t end, Getter &getter)

template<class AlephIt >
void	fill_from_aleph_it (AlephIt it)

Private Attributes
Array< T >	tree

size_t	n = 0

T	identity

Op	op

Detailed Description

template<typename T, class Op>
requires SegmentTreeOp<Op, T>
class Aleph::Gen_Segment_Tree< T, Op >

Segment tree over an arbitrary associative binary operation.

This is the classical segment tree supporting:

Point updates in O(log n)
Range queries in O(log n)

It maintains an implicit binary tree backed by Array<T>, using 1-based node indexing and allocating roughly 4*n nodes.

Unlike Sparse Table, the operation need not be idempotent. Unlike Fenwick Tree, the operation need not be invertible. Only associativity is required.

Identity element: Queries rely on an identity element id such that op(id, x) == x and op(x, id) == x.

Update semantics: update(i, delta) applies a[i] = op(a[i], delta). Use set(i, val) if you need assignment semantics.

Template Parameters

T	element type.
Op	associative binary functor.

Example: // Range-sum segment tree

Gen_Segment_Tree<int, Aleph::plus<int>> st = {3, 1, 4, 1, 5};

st.query(1, 3); // 1 + 4 + 1 = 6

st.update(2, 10); // a[2] += 10 => {3, 1, 14, 1, 5}

st.query(1, 3); // 1 + 14 + 1 = 16

Aleph::Gen_Segment_Tree
Segment tree over an arbitrary associative binary operation.
Definition tpl_segment_tree.H:149

Aleph::Gen_Segment_Tree::query
T query(const size_t l, const size_t r) const
Range query over [l, r].
Definition tpl_segment_tree.H:389

Aleph::Gen_Segment_Tree::update
void update(const size_t i, const T &delta)
Point update: a[i] = Op(a[i], delta).
Definition tpl_segment_tree.H:358

Definition at line 148 of file tpl_segment_tree.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Op >

using Aleph::Gen_Segment_Tree< T, Op >::Item_Type = T

Definition at line 252 of file tpl_segment_tree.H.

Constructor & Destructor Documentation

◆ Gen_Segment_Tree() [1/7]

template<typename T , class Op >

Aleph::Gen_Segment_Tree< T, Op >::Gen_Segment_Tree	(	const size_t	num,
		const T &	init_val,
		const T &	id,
		Op	oper = `Op()`
	)

inline

Construct a segment tree with num elements, all equal to init_val.

Parameters

num	number of elements.
init_val	value for every position.
id	identity element of the monoid.
oper	associative binary functor.

Definition at line 262 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::fill_and_build(), and Aleph::Gen_Segment_Tree< T, Op >::n.

◆ Gen_Segment_Tree() [2/7]

template<typename T , class Op >

Aleph::Gen_Segment_Tree< T, Op >::Gen_Segment_Tree	(	std::initializer_list< T >	il,
		const T &	id,
		Op	oper = `Op()`
	)

inline

Construct from an initializer list.

Parameters

il	initializer list with the element values.
id	identity element of the monoid.
oper	associative binary functor.

Example: Gen_Segment_Tree<int, Aleph::plus<int>> st({3, 1, 4}, 0);

assert(st.query(0, 2) == 8); // 3 + 1 + 4

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Definition at line 283 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Segment_Tree< T, Op >::fill_and_build(), and Aleph::Gen_Segment_Tree< T, Op >::n.