Loading...
Searching...
No Matches
Aleph::HLD_Max< GT, T, SA > Struct Template Reference
HLD with path/subtree max queries. More...
#include <HLD.H>
Inheritance diagram for Aleph::HLD_Max< GT, T, SA >:
Collaboration diagram for Aleph::HLD_Max< GT, T, SA >:
Public Types | |
| using | Base = Gen_HLD< GT, T, Max_Op< T >, SA > |
| using | Node = typename GT::Node |
 Public Types inherited from Aleph::Gen_HLD< GT, T, Op, SA > | |
| using | Node = typename GT::Node |
Public Member Functions | |
| template<class NodeValueFn > | |
| HLD_Max (const GT &g, Node *root, NodeValueFn &&nv, SA sa=SA()) | |
| template<class NodeValueFn > | |
| HLD_Max (const GT &g, NodeValueFn &&nv, SA sa=SA()) | |
| Public Member Functions inherited from Aleph::Gen_HLD< GT, T, Op, SA > | |
| 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. | |
Detailed Description
HLD with path/subtree max queries.
- Template Parameters
-
GT Graph type. T Totally ordered value type (identity = lowest()).SA Arc filter type.
Member Typedef Documentation
◆ Base
◆ Node
Constructor & Destructor Documentation
◆ HLD_Max() [1/2]
template<class NodeValueFn >
|
inline |
◆ HLD_Max() [2/2]
template<class NodeValueFn >
|
inline |
The documentation for this struct was generated from the following file:
