Segment-tree-powered path/subtree queries over an HLD layout. More...

#include <Tree_Decomposition.H>

Collaboration diagram for Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >:

Public Types
using	Node = typename GT::Node

Public Member Functions
	Gen_HLD_Path_Query (const GT &g, Node *root, const T &identity, Op op=Op(), SA sa=SA())
	Construct from graph/root using `node->get_info()` as initial values.

	Gen_HLD_Path_Query (const GT &g, const T &identity, Op op=Op(), SA sa=SA())
	Construct from graph (first node as root) using `node->get_info()`.

template<class Getter > requires std::invocable<Getter, Node *>
and std::convertible_to< std::invoke_result_t< Getter, Node * >, T >	Gen_HLD_Path_Query (const GT &g, Node *root, Getter getter, const T &identity, Op op=Op(), SA sa=SA())
	Construct with custom node-to-value getter.

template<class Getter > requires std::invocable<Getter, Node *>
and std::convertible_to< std::invoke_result_t< Getter, Node * >, T >	Gen_HLD_Path_Query (const GT &g, Getter getter, const T &identity, Op op=Op(), SA sa=SA())
	Construct with custom getter and implicit root (first node).

const Gen_Heavy_Light_Decomposition< GT, SA > &	decomposition () const noexcept

size_t	size () const noexcept

bool	is_empty () const noexcept

T	query_path_id (const size_t u, const size_t v) const
	Path query between two node IDs in O(log^2 n).

T	query_path (const Node u, const Node v) const
	Path query between two nodes in O(log^2 n).

T	query_subtree_id (const size_t id) const
	Subtree query for node ID in O(log n).

T	query_subtree (const Node *node) const
	Subtree query for node in O(log n).

void	update_node_id (const size_t id, const T &delta)
	Point update: `a[id] = Op(a[id], delta)`.

void	update_node (const Node *node, const T &delta)
	Point update: `a[node] = Op(a[node], delta)`.

void	set_node_id (const size_t id, const T &value)
	Point assignment: `a[id] = value`.

void	set_node (const Node *node, const T &value)
	Point assignment: `a[node] = value`.

T	get_node_id (const size_t id) const
	Return current value at node ID.

T	get_node (const Node *node) const
	Return current value at node.

Private Member Functions
void	ensure_not_empty (const char *where) const

Static Private Member Functions
template<class Getter > requires std::invocable<Getter, Node *>
and static std::convertible_to< std::invoke_result_t< Getter, Node * >, T > Array< T >	build_base_array (const Gen_Heavy_Light_Decomposition< GT, SA > &hld, Getter getter)

static Array< T >	build_base_from_node_info (const Gen_Heavy_Light_Decomposition< GT, SA > &hld)

Private Attributes
Gen_Heavy_Light_Decomposition< GT, SA >	hld_

Gen_Segment_Tree< T, Op >	segment_tree_

T	identity_

Op	op_

Detailed Description

template<class GT, typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>
class Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >

Segment-tree-powered path/subtree queries over an HLD layout.

This class combines Gen_Heavy_Light_Decomposition with Gen_Segment_Tree for convenient dynamic queries.

Supported operations:

query_path(u, v)
query_subtree(u)
update_node(u, delta)
set_node(u, value)
get_node(u)

Note: query_path() combines segment answers with Op and therefore assumes this fold is valid for your query semantics. For non-commutative path queries, use for_each_path_segment_id() from Gen_Heavy_Light_Decomposition and handle direction explicitly.

Template Parameters

GT	Graph type.
T	Segment value type.
Op	Associative operation.
SA	Arc filter type.

Definition at line 811 of file Tree_Decomposition.H.

Member Typedef Documentation

◆ Node

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

using Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::Node = typename GT::Node

Definition at line 814 of file Tree_Decomposition.H.

Constructor & Destructor Documentation

◆ Gen_HLD_Path_Query() [1/4]

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::Gen_HLD_Path_Query	(	const GT &	g,
		Node *	root,
		const T &	identity,
		Op	op = `Op()`,
		SA	sa = `SA()`
	)

inline

Construct from graph/root using node->get_info() as initial values.

Definition at line 858 of file Tree_Decomposition.H.

◆ Gen_HLD_Path_Query() [2/4]

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::Gen_HLD_Path_Query	(	const GT &	g,
		const T &	identity,
		Op	op = `Op()`,
		SA	sa = `SA()`
	)

inline

Construct from graph (first node as root) using node->get_info().

Definition at line 872 of file Tree_Decomposition.H.

◆ Gen_HLD_Path_Query() [3/4]

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

template<class Getter >
requires std::invocable<Getter, Node *>

and std::convertible_to< std::invoke_result_t< Getter, Node * >, T > Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::Gen_HLD_Path_Query	(	const GT &	g,
		Node *	root,
		Getter	getter,
		const T &	identity,
		Op	op = `Op()`,
		SA	sa = `SA()`
	)

inline

Construct with custom node-to-value getter.

Definition at line 888 of file Tree_Decomposition.H.

◆ Gen_HLD_Path_Query() [4/4]

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

template<class Getter >
requires std::invocable<Getter, Node *>

and std::convertible_to< std::invoke_result_t< Getter, Node * >, T > Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::Gen_HLD_Path_Query	(	const GT &	g,
		Getter	getter,
		const T &	identity,
		Op	op = `Op()`,
		SA	sa = `SA()`
	)

inline

Construct with custom getter and implicit root (first node).

Definition at line 906 of file Tree_Decomposition.H.

Member Function Documentation

◆ build_base_array()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

template<class Getter >
requires std::invocable<Getter, Node *>

and static std::convertible_to< std::invoke_result_t< Getter, Node * >, T > Array< T > Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::build_base_array	(	const Gen_Heavy_Light_Decomposition< GT, SA > &	hld,
		Getter	getter
	)

inlinestaticprivate

Definition at line 830 of file Tree_Decomposition.H.

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

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::build_base_from_node_info().

◆ build_base_from_node_info()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

static Array< T > Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::build_base_from_node_info ( const Gen_Heavy_Light_Decomposition< GT, SA > & hld )

inlinestaticprivate

Definition at line 847 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::build_base_array(), and Aleph::divide_and_conquer_partition_dp().

◆ decomposition()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

const Gen_Heavy_Light_Decomposition< GT, SA > & Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::decomposition ( ) const

inlinenoexcept

Definition at line 919 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_.

Referenced by TYPED_TEST().

◆ ensure_not_empty()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty ( const char * where ) const

inlineprivate

Definition at line 822 of file Tree_Decomposition.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::is_empty().

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::get_node_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node_id(), and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node_id().

◆ get_node()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::get_node ( const Node * node ) const

inline

Return current value at node.

Definition at line 997 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::get_node_id(), and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_.

◆ get_node_id()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::get_node_id ( const size_t id ) const

inline

Return current value at node ID.

Definition at line 990 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::segment_tree_.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::get_node().

◆ is_empty()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

bool Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::is_empty ( ) const

inlinenoexcept

Definition at line 925 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty(), and TYPED_TEST().

◆ query_path()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path	(	const Node *	u,
		const Node *	v
	)		const

inline

Path query between two nodes in O(log^2 n).

Definition at line 944 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id().

Referenced by TYPED_TEST(), TYPED_TEST(), and TYPED_TEST().

◆ query_path_id()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id	(	const size_t	u,
		const size_t	v
	)		const

inline

Path query between two node IDs in O(log^2 n).

Definition at line 928 of file Tree_Decomposition.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::identity_, l, Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::op_, r, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::segment_tree_.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path(), and TYPED_TEST().

◆ query_subtree()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree ( const Node * node ) const

inline

Subtree query for node in O(log n).

Definition at line 958 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree_id().

Referenced by TYPED_TEST(), and TYPED_TEST().

◆ query_subtree_id()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree_id ( const size_t id ) const

inline

Subtree query for node ID in O(log n).

Definition at line 950 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, Aleph::range(), and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::segment_tree_.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree().

◆ set_node()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node	(	const Node *	node,
		const T &	value
	)

inline

Point assignment: a[node] = value.

Definition at line 984 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node_id().

Referenced by TYPED_TEST(), and TYPED_TEST().

◆ set_node_id()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node_id	(	const size_t	id,
		const T &	value
	)

inline

Point assignment: a[id] = value.

Definition at line 977 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::segment_tree_.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node().

◆ size()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::size ( ) const

inlinenoexcept

Definition at line 924 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_.

◆ update_node()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node	(	const Node *	node,
		const T &	delta
	)

inline

Point update: a[node] = Op(a[node], delta).

Definition at line 971 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node_id().

Referenced by TYPED_TEST(), and TYPED_TEST().

◆ update_node_id()

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

void Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node_id	(	const size_t	id,
		const T &	delta
	)

inline

Point update: a[id] = Op(a[id], delta).

Definition at line 964 of file Tree_Decomposition.H.

References Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_, and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::segment_tree_.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node().

Member Data Documentation

◆ hld_

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

Gen_Heavy_Light_Decomposition<GT, SA> Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::hld_

private

Definition at line 817 of file Tree_Decomposition.H.

◆ identity_

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

T Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::identity_

private

Definition at line 819 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id().

◆ op_

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

Op Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::op_

private

Definition at line 820 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id().

◆ segment_tree_

template<class GT , typename T = typename GT::Node::Node_Type, class Op = Aleph::plus<T>, class SA = Dft_Show_Arc<GT>>

Gen_Segment_Tree<T, Op> Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::segment_tree_

private

Definition at line 818 of file Tree_Decomposition.H.

Referenced by Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::get_node_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_path_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::query_subtree_id(), Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::set_node_id(), and Aleph::Gen_HLD_Path_Query< GT, T, Op, SA >::update_node_id().

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

Tree_Decomposition.H

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Node

Constructor & Destructor Documentation

◆ Gen_HLD_Path_Query() [1/4]

◆ Gen_HLD_Path_Query() [2/4]

◆ Gen_HLD_Path_Query() [3/4]

◆ Gen_HLD_Path_Query() [4/4]

Member Function Documentation

◆ build_base_array()

◆ build_base_from_node_info()

◆ decomposition()

◆ ensure_not_empty()

◆ get_node()

◆ get_node_id()

◆ is_empty()

◆ query_path()

◆ query_path_id()

◆ query_subtree()

◆ query_subtree_id()

◆ set_node()

◆ set_node_id()

◆ size()

◆ update_node()

◆ update_node_id()

Member Data Documentation

◆ hld_

◆ identity_

◆ op_

◆ segment_tree_