Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
Aleph::Gen_HLD< GT, T, Op, SA > Class Template Reference
Graphs

Heavy-Light Decomposition with segment tree for path/subtree queries. More...

#include <HLD.H>

Inheritance diagram for Aleph::Gen_HLD< GT, T, Op, SA >:
[legend]
Collaboration diagram for Aleph::Gen_HLD< GT, T, Op, SA >:
[legend]

Public Types

using Node = typename GT::Node
 

Public Member Functions

template<class NodeValueFn >
 Gen_HLD (const GT &g, Node *root, NodeValueFn &&node_value, const T &identity, Op oper=Op(), SA sa=SA())
 Construct HLD from graph, root, and node value functor.
 
template<class NodeValueFn >
 Gen_HLD (const GT &g, NodeValueFn &&node_value, const T &identity, Op oper=Op(), SA sa=SA())
 Construct with first graph node as root.
 
size_t size () const noexcept
 Total number of nodes in the tree.
 
bool is_empty () const noexcept
 Returns true if the tree has no nodes.
 
Node * root () const noexcept
 Returns the root node.
 
size_t root_id () const noexcept
 Returns the internal ID of the root node.
 
Node * node_of (const size_t id) const
 Map an internal ID back to a Node pointer.
 
size_t id_of (const Node *node) const
 Map a Node pointer to its internal ID.
 
size_t position (const size_t id) const
 HLD flat-array position of node id.
 
size_t chain_head_id (const size_t id) const
 Head of the chain containing node id.
 
size_t depth_of_id (const size_t id) const
 Depth of node id from root.
 
size_t depth_of (const Node *node) const
 Depth of node from root.
 
size_t subtree_size_of_id (const size_t id) const
 Subtree size of node id.
 
size_t subtree_size_of (const Node *node) const
 Subtree size of node.
 
size_t parent_id (const size_t id) const
 Parent ID of node id, or NONE if root.
 
Node * parent_of (const Node *node) const
 Parent of node, or nullptr if root.
 
size_t num_chains () const noexcept
 Number of heavy chains in the decomposition.
 
T path_query_id (size_t u, size_t v) const
 Path query by node IDs in O(log^2 n).
 
T path_query (const Node *u, const Node *v) const
 Path query by node pointers in O(log^2 n).
 
T path_query_edges_id (size_t u, size_t v) const
 Edge-weighted path query by node IDs in O(log^2 n).
 
T path_query_edges (const Node *u, const Node *v) const
 Edge-weighted path query by node pointers.
 
T subtree_query_id (const size_t v) const
 Subtree query by node ID in O(log n).
 
T subtree_query (const Node *v) const
 Subtree query by node pointer in O(log n).
 
void point_update_id (const size_t v, const T &new_value)
 Point update by node ID: set value to new_value.
 
void point_update (const Node *v, const T &new_value)
 Point update by node pointer: set value to new_value.
 
size_t lca_id (size_t u, size_t v) const
 LCA query by node IDs in O(log n).
 
Node * lca (const Node *u, const Node *v) const
 LCA query by node pointers in O(log n).
 
size_t distance_id (const size_t u, const size_t v) const
 Number of edges between two nodes by IDs in O(log n).
 
size_t distance (const Node *u, const Node *v) const
 Number of edges between two nodes in O(log n).
 
const Array< size_t > & position_array () const noexcept
 Read-only access to the flat-position array.
 
const Array< size_t > & chain_head_array () const noexcept
 Read-only access to the chain-head array.
 
const Array< size_t > & depth_array () const noexcept
 Read-only access to the depth array.
 
const Array< size_t > & subtree_size_array () const noexcept
 Read-only access to the subtree-size array.
 
const Array< size_t > & parent_array () const noexcept
 Read-only access to the parent array.
 
T get_value_at_id (const size_t id) const
 Current node value at HLD position pos in the segment tree.
 
T get_value (const Node *v) const
 Current node value at node pointer v.
 

Private Types

using Topology = hld_detail::HLD_Tree_Data< GT, SA >
 

Private Member Functions

size_t n () const noexcept
 
void ensure_not_empty (const char *where) const
 
template<class NodeValueFn >
void build_segment_tree (NodeValueFn &&node_value)
 

Private Attributes

Topology topology_
 
T identity_
 
Op op_
 
Gen_Segment_Tree< T, Op > seg_
 

Static Private Attributes

static constexpr size_t NONE = Topology::NONE
 

Detailed Description

template<class GT, typename T, class Op, class SA = Dft_Show_Arc<GT>>
requires SegmentTreeOp<Op, T>
class Aleph::Gen_HLD< GT, T, Op, SA >

Heavy-Light Decomposition with segment tree for path/subtree queries.

Decomposes a rooted tree into heavy chains and maintains a segment tree over the flattened HLD order. Supports path queries, subtree queries, point updates, LCA computation, and distance queries.

Template Parameters
GTGraph type (List_Graph, List_SGraph, Array_Graph).
TValue type stored at each node.
OpAssociative and commutative binary functor over T.
SAArc filter type (default: Dft_Show_Arc<GT>).
Complexity
Operation Time
Construction O(n log n)
path_query O(log^2 n)
subtree_query O(log n)
point_update O(log n)
lca O(log n)
distance O(log n)

Definition at line 526 of file HLD.H.

Member Typedef Documentation

◆ Node

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
using Aleph::Gen_HLD< GT, T, Op, SA >::Node = typename GT::Node

Definition at line 529 of file HLD.H.

◆ Topology

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
using Aleph::Gen_HLD< GT, T, Op, SA >::Topology = hld_detail::HLD_Tree_Data<GT, SA>
private

Definition at line 532 of file HLD.H.

Constructor & Destructor Documentation

◆ Gen_HLD() [1/2]

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
template<class NodeValueFn >
Aleph::Gen_HLD< GT, T, Op, SA >::Gen_HLD ( const GT &  g,
Node *  root,
NodeValueFn &&  node_value,
const T &  identity,
Op  oper = Op(),
SA  sa = SA() 
)
inline

Construct HLD from graph, root, and node value functor.

Parameters
[in]gTree topology (filtered by sa).
[in]rootRoot node pointer (must belong to g).
[in]node_valueCallable Node* -> T providing node values.
[in]identityIdentity element of the monoid (T, Op).
[in]operAssociative binary functor.
[in]saArc filter.
Exceptions
ah_domain_errorif the filtered graph is not a tree.

Definition at line 580 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree(), and Aleph::divide_and_conquer_partition_dp().

◆ Gen_HLD() [2/2]

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
template<class NodeValueFn >
Aleph::Gen_HLD< GT, T, Op, SA >::Gen_HLD ( const GT &  g,
NodeValueFn &&  node_value,
const T &  identity,
Op  oper = Op(),
SA  sa = SA() 
)
inline

Construct with first graph node as root.

Definition at line 592 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree(), and Aleph::divide_and_conquer_partition_dp().

Member Function Documentation

◆ build_segment_tree()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
template<class NodeValueFn >
void Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree ( NodeValueFn &&  node_value)
inlineprivate

Definition at line 549 of file HLD.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::id_to_node(), Aleph::Gen_HLD< GT, T, Op, SA >::identity_, Aleph::Gen_HLD< GT, T, Op, SA >::is_empty(), Aleph::Gen_HLD< GT, T, Op, SA >::n(), Aleph::Gen_HLD< GT, T, Op, SA >::op_, Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), Aleph::Gen_HLD< GT, T, Op, SA >::seg_, and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::Gen_HLD(), and Aleph::Gen_HLD< GT, T, Op, SA >::Gen_HLD().

◆ chain_head_array()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
const Array< size_t > & Aleph::Gen_HLD< GT, T, Op, SA >::chain_head_array ( ) const
inlinenoexcept

Read-only access to the chain-head array.

chain_head_array()(id) gives the ID of the head of the chain containing node id.

Definition at line 890 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::chain_head(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ chain_head_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::chain_head_id ( const size_t  id) const
inline

Head of the chain containing node id.

Definition at line 634 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::chain_head(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

◆ depth_array()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
const Array< size_t > & Aleph::Gen_HLD< GT, T, Op, SA >::depth_array ( ) const
inlinenoexcept

Read-only access to the depth array.

Definition at line 896 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::depth(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ depth_of()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::depth_of ( const Node *  node) const
inline

Depth of node from root.

Definition at line 648 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::depth_of_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::id_of().

◆ depth_of_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::depth_of_id ( const size_t  id) const
inline

Depth of node id from root.

Definition at line 641 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::depth(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::depth_of().

◆ distance()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::distance ( const Node *  u,
const Node *  v 
) const
inline

Number of edges between two nodes in O(log n).

Definition at line 867 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::distance_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::id_of().

◆ distance_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::distance_id ( const size_t  u,
const size_t  v 
) const
inline

Number of edges between two nodes by IDs in O(log n).

Definition at line 859 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::depth(), Aleph::Gen_HLD< GT, T, Op, SA >::lca_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::distance().

◆ ensure_not_empty()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
void Aleph::Gen_HLD< GT, T, Op, SA >::ensure_not_empty ( const char *  where) const
inlineprivate

Definition at line 542 of file HLD.H.

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

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::lca_id(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id(), Aleph::Gen_HLD< GT, T, Op, SA >::point_update_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query_id().

◆ get_value()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::get_value ( const Node *  v) const
inline

Current node value at node pointer v.

Definition at line 921 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::get_value_at_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::id_of().

◆ get_value_at_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::get_value_at_id ( const size_t  id) const
inline

Current node value at HLD position pos in the segment tree.

Definition at line 914 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), Aleph::Gen_HLD< GT, T, Op, SA >::seg_, Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::get_value().

◆ id_of()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::id_of ( const Node *  node) const
inline

Map a Node pointer to its internal ID.

Definition at line 621 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::id_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::depth_of(), Aleph::Gen_HLD< GT, T, Op, SA >::distance(), Aleph::Gen_HLD< GT, T, Op, SA >::get_value(), Aleph::Gen_HLD< GT, T, Op, SA >::lca(), Aleph::Gen_HLD< GT, T, Op, SA >::parent_of(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges(), Aleph::Gen_HLD< GT, T, Op, SA >::point_update(), Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query(), and Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_of().

◆ is_empty()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
bool Aleph::Gen_HLD< GT, T, Op, SA >::is_empty ( ) const
inlinenoexcept

Returns true if the tree has no nodes.

Definition at line 606 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::is_empty(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

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

◆ lca()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_HLD< GT, T, Op, SA >::lca ( const Node *  u,
const Node *  v 
) const
inline

LCA query by node pointers in O(log n).

Definition at line 849 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), Aleph::Gen_HLD< GT, T, Op, SA >::lca_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::node_of().

◆ lca_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::lca_id ( size_t  u,
size_t  v 
) const
inline

LCA query by node IDs in O(log n).

Definition at line 830 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::chain_head(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::depth(), Aleph::Gen_HLD< GT, T, Op, SA >::ensure_not_empty(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::parent(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::distance_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::lca().

◆ n()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::n ( ) const
inlineprivatenoexcept

Definition at line 540 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::size(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree().

◆ node_of()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_HLD< GT, T, Op, SA >::node_of ( const size_t  id) const
inline

Map an internal ID back to a Node pointer.

Definition at line 615 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::node_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::lca(), and Aleph::Gen_HLD< GT, T, Op, SA >::parent_of().

◆ num_chains()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::num_chains ( ) const
inlinenoexcept

Number of heavy chains in the decomposition.

Definition at line 681 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::num_chains(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ parent_array()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
const Array< size_t > & Aleph::Gen_HLD< GT, T, Op, SA >::parent_array ( ) const
inlinenoexcept

Read-only access to the parent array.

Definition at line 908 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::parent(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ parent_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::parent_id ( const size_t  id) const
inline

Parent ID of node id, or NONE if root.

Definition at line 667 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::parent(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::parent_of().

◆ parent_of()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_HLD< GT, T, Op, SA >::parent_of ( const Node *  node) const
inline

Parent of node, or nullptr if root.

Definition at line 674 of file HLD.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), Aleph::Gen_HLD< GT, T, Op, SA >::node_of(), Aleph::Gen_HLD< GT, T, Op, SA >::NONE, and Aleph::Gen_HLD< GT, T, Op, SA >::parent_id().

◆ path_query()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::path_query ( const Node *  u,
const Node *  v 
) const
inline

Path query by node pointers in O(log^2 n).

Definition at line 731 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id().

◆ path_query_edges()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges ( const Node *  u,
const Node *  v 
) const
inline

Edge-weighted path query by node pointers.

Definition at line 773 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id().

◆ path_query_edges_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id ( size_t  u,
size_t  v 
) const
inline

Edge-weighted path query by node IDs in O(log^2 n).

Like path_query_id but skips the LCA node value, useful when values represent edges (stored on the child node).

Definition at line 741 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::chain_head(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::depth(), Aleph::Gen_HLD< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD< GT, T, Op, SA >::identity_, Aleph::Gen_HLD< GT, T, Op, SA >::op_, Aleph::hld_detail::HLD_Tree_Data< GT, SA >::parent(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), Aleph::Gen_HLD< GT, T, Op, SA >::seg_, Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges().

◆ path_query_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id ( size_t  u,
size_t  v 
) const
inline

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

Combines all node values on the path from u to v using the binary operation Op.

Parameters
[in]uSource node ID.
[in]vTarget node ID.
Returns
Combined value along the path.

Definition at line 699 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::chain_head(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::depth(), Aleph::Gen_HLD< GT, T, Op, SA >::ensure_not_empty(), Aleph::Gen_HLD< GT, T, Op, SA >::identity_, Aleph::Gen_HLD< GT, T, Op, SA >::op_, Aleph::hld_detail::HLD_Tree_Data< GT, SA >::parent(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), Aleph::Gen_HLD< GT, T, Op, SA >::seg_, Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::path_query().

◆ point_update()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
void Aleph::Gen_HLD< GT, T, Op, SA >::point_update ( const Node *  v,
const T &  new_value 
)
inline

Point update by node pointer: set value to new_value.

Definition at line 820 of file HLD.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::point_update_id().

◆ point_update_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
void Aleph::Gen_HLD< GT, T, Op, SA >::point_update_id ( const size_t  v,
const T &  new_value 
)
inline

Point update by node ID: set value to new_value.

Parameters
[in]vNode ID.
[in]new_valueNew value for the node.

Definition at line 811 of file HLD.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_HLD< GT, T, Op, SA >::ensure_not_empty(), Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), Aleph::Gen_HLD< GT, T, Op, SA >::seg_, Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::point_update().

◆ position()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::position ( const size_t  id) const
inline

HLD flat-array position of node id.

Definition at line 627 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

◆ position_array()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
const Array< size_t > & Aleph::Gen_HLD< GT, T, Op, SA >::position_array ( ) const
inlinenoexcept

Read-only access to the flat-position array.

position_array()(id) gives the segment-tree index of node id.

Definition at line 880 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ root()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_HLD< GT, T, Op, SA >::root ( ) const
inlinenoexcept

Returns the root node.

Definition at line 609 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::root(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ root_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::root_id ( ) const
inlinenoexcept

Returns the internal ID of the root node.

Definition at line 612 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::root_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ size()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::size ( ) const
inlinenoexcept

Total number of nodes in the tree.

Definition at line 603 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::size(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ subtree_query()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query ( const Node *  v) const
inline

Subtree query by node pointer in O(log n).

Definition at line 797 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query_id().

◆ subtree_query_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query_id ( const size_t  v) const
inline

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

Combines all values in the subtree rooted at v.

Definition at line 786 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::ensure_not_empty(), l, Aleph::hld_detail::HLD_Tree_Data< GT, SA >::pos(), r, Aleph::Gen_HLD< GT, T, Op, SA >::seg_, Aleph::hld_detail::HLD_Tree_Data< GT, SA >::subtree_size(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query().

◆ subtree_size_array()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
const Array< size_t > & Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_array ( ) const
inlinenoexcept

Read-only access to the subtree-size array.

Definition at line 902 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::subtree_size(), and Aleph::Gen_HLD< GT, T, Op, SA >::topology_.

◆ subtree_size_of()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_of ( const Node *  node) const
inline

Subtree size of node.

Definition at line 661 of file HLD.H.

References Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), and Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_of_id().

◆ subtree_size_of_id()

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_of_id ( const size_t  id) const
inline

Subtree size of node id.

Definition at line 654 of file HLD.H.

References Aleph::hld_detail::HLD_Tree_Data< GT, SA >::subtree_size(), Aleph::Gen_HLD< GT, T, Op, SA >::topology_, and Aleph::hld_detail::HLD_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_of().

Member Data Documentation

◆ identity_

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
T Aleph::Gen_HLD< GT, T, Op, SA >::identity_
private

Definition at line 536 of file HLD.H.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id().

◆ NONE

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
constexpr size_t Aleph::Gen_HLD< GT, T, Op, SA >::NONE = Topology::NONE
staticconstexprprivate

Definition at line 533 of file HLD.H.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::parent_of().

◆ op_

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Op Aleph::Gen_HLD< GT, T, Op, SA >::op_
private

Definition at line 537 of file HLD.H.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id().

◆ seg_

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Gen_Segment_Tree<T, Op> Aleph::Gen_HLD< GT, T, Op, SA >::seg_
private

Definition at line 538 of file HLD.H.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree(), Aleph::Gen_HLD< GT, T, Op, SA >::get_value_at_id(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id(), Aleph::Gen_HLD< GT, T, Op, SA >::point_update_id(), and Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query_id().

◆ topology_

template<class GT , typename T , class Op , class SA = Dft_Show_Arc<GT>>
Topology Aleph::Gen_HLD< GT, T, Op, SA >::topology_
private

Definition at line 535 of file HLD.H.

Referenced by Aleph::Gen_HLD< GT, T, Op, SA >::build_segment_tree(), Aleph::Gen_HLD< GT, T, Op, SA >::chain_head_array(), Aleph::Gen_HLD< GT, T, Op, SA >::chain_head_id(), Aleph::Gen_HLD< GT, T, Op, SA >::depth_array(), Aleph::Gen_HLD< GT, T, Op, SA >::depth_of_id(), Aleph::Gen_HLD< GT, T, Op, SA >::distance_id(), Aleph::Gen_HLD< GT, T, Op, SA >::get_value_at_id(), Aleph::Gen_HLD< GT, T, Op, SA >::id_of(), Aleph::Gen_HLD< GT, T, Op, SA >::is_empty(), Aleph::Gen_HLD< GT, T, Op, SA >::lca_id(), Aleph::Gen_HLD< GT, T, Op, SA >::n(), Aleph::Gen_HLD< GT, T, Op, SA >::node_of(), Aleph::Gen_HLD< GT, T, Op, SA >::num_chains(), Aleph::Gen_HLD< GT, T, Op, SA >::parent_array(), Aleph::Gen_HLD< GT, T, Op, SA >::parent_id(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_edges_id(), Aleph::Gen_HLD< GT, T, Op, SA >::path_query_id(), Aleph::Gen_HLD< GT, T, Op, SA >::point_update_id(), Aleph::Gen_HLD< GT, T, Op, SA >::position(), Aleph::Gen_HLD< GT, T, Op, SA >::position_array(), Aleph::Gen_HLD< GT, T, Op, SA >::root(), Aleph::Gen_HLD< GT, T, Op, SA >::root_id(), Aleph::Gen_HLD< GT, T, Op, SA >::size(), Aleph::Gen_HLD< GT, T, Op, SA >::subtree_query_id(), Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_array(), and Aleph::Gen_HLD< GT, T, Op, SA >::subtree_size_of_id().

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