Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
The Heavy-Light Decomposition class. More...
Public Member Functions | |
HLD (int nodes) | |
Class parameterized constructor. Resizes the and initilizes the data members. | |
void | init () |
This function must be called after the tree adjacency list and node values are populated The function initializes the required parametes, and populates the segment tree. | |
void | update (int node, X val) |
This function updates the value at node with val. | |
X | query (int a, int b) |
This function returns the sum of node values in the simple path from from node_1 to node_2. | |
Public Member Functions inherited from range_queries::heavy_light_decomposition::Tree< X > | |
Tree (int nodes) | |
Class parameterized constructor, resizes the and initializes the data members. | |
void | add_edge (const int u, const int v) |
Adds an undirected edge from node u to node v in the tree. | |
void | change_root (int new_root) |
Set the root for the tree. | |
void | set_node_val (const std::vector< X > &node_val) |
Set the values for all the nodes. | |
void | init () |
This function must be called after the tree adjacency list and node values are populated The function initializes the required parameters, and populates the segment tree. | |
void | lift (int *const p, int dist) |
The function lifts a node, k units up the tree. The lifting is done in place, and the result is stored in the address pointed by p. | |
int | kth_ancestor (int p, const int &dist) |
The function returns the kth ancestor of a node. | |
int | lca (int a, int b) |
The function returns the least common ancestor of two nodes. | |
Private Member Functions | |
void | dfs_hc (int u, int p=-1) |
Utility function to assign heavy child to each node (-1 for a leaf node) | |
void | dfs_par (int u, int p=-1) |
Utility function to assign highest parent that can be reached though heavy chains. | |
void | dfs_labels (int u, int p=-1) |
Utility function to lable the nodes so that heavy chains have a contigous lable. | |
X | chain_query (int a, int b) |
Utility function to break down a path query into two chain queries. | |
Private Attributes | |
int | label |
utility member to assign labels in dfs_labels() | |
std::vector< int > | h_label |
stores the label of a node | |
std::vector< int > | h_heavychlid |
stores the heavy child of a node | |
std::vector< int > | h_parent |
stores the top of the heavy chain from a node | |
The Heavy-Light Decomposition class.
the | data type of the values stored in the tree nodes |
|
inlineexplicit |
Class parameterized constructor. Resizes the and initilizes the data members.
nodes | the total number of nodes in the tree |
|
inlineprivate |
Utility function to break down a path query into two chain queries.
a | node where the path starts |
b | node where the path ends a and b must belong to a single root to leaf chain |
|
inlineprivate |
Utility function to assign heavy child to each node (-1 for a leaf node)
u | current dfs node |
p | the parent of node u |
|
inlineprivate |
Utility function to lable the nodes so that heavy chains have a contigous lable.
u | current dfs node |
p | the parent of node u |
|
inlineprivate |
Utility function to assign highest parent that can be reached though heavy chains.
u | current dfs node |
p | the parent of node u |
|
inline |
This function must be called after the tree adjacency list and node values are populated The function initializes the required parametes, and populates the segment tree.
|
inline |
This function returns the sum of node values in the simple path from from node_1 to node_2.
a | the node where the simple path starts |
b | the node where the simple path ends (parameters are interchangeable, i.e., the function is commutative) |
|
inline |
This function updates the value at node with val.
node | the node where the update is done |
val | the value that is being updated |