Algorithms_in_C++
1.0.0
Set of algorithms implemented in C++.
|
The Heavy-Light Decomposition class.
More...
|
| HLD (int nodes) |
| Class parameterized constructor. Resizes the and initilizes the data members. More...
|
|
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. More...
|
|
void | update (int node, X val) |
| This function updates the value at node with val. More...
|
|
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. More...
|
|
| Tree (int nodes) |
| Class parameterized constructor, resizes the and initializes the data members. More...
|
|
void | add_edge (const int u, const int v) |
| Adds an undirected edge from node u to node v in the tree. More...
|
|
void | change_root (int new_root) |
| Set the root for the tree. More...
|
|
void | set_node_val (const std::vector< X > &node_val) |
| Set the values for all the nodes. More...
|
|
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. More...
|
|
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. More...
|
|
int | kth_ancestor (int p, const int &dist) |
| The function returns the kth ancestor of a node. More...
|
|
int | lca (int a, int b) |
| The function returns the least common ancestor of two nodes. More...
|
|
|
void | dfs_hc (int u, int p=-1) |
| Utility function to assign heavy child to each node (-1 for a leaf node) More...
|
|
void | dfs_par (int u, int p=-1) |
| Utility function to assign highest parent that can be reached though heavy chains. More...
|
|
void | dfs_labels (int u, int p=-1) |
| Utility function to lable the nodes so that heavy chains have a contigous lable. More...
|
|
X | chain_query (int a, int b) |
| Utility function to break down a path query into two chain queries. More...
|
|
template<typename X>
class range_queries::heavy_light_decomposition::HLD< X >
The Heavy-Light Decomposition class.
- Template Parameters
-
the | data type of the values stored in the tree nodes |
◆ HLD()
Class parameterized constructor. Resizes the and initilizes the data members.
- Parameters
-
nodes | the total number of nodes in the tree |
435 : Tree<X>(nodes), SG<X>(nodes) {
◆ chain_query()
Utility function to break down a path query into two chain queries.
- Parameters
-
a | node where the path starts |
b | node where the path ends a and b must belong to a single root to leaf chain |
- Returns
- the sum of ndoe values in the simple path from a to b
◆ dfs_hc()
Utility function to assign heavy child to each node (-1 for a leaf node)
- Parameters
-
u | current dfs node |
p | the parent of node u |
- Returns
- void
351 int hc_size = -1, hc_id = -1;
◆ dfs_labels()
Utility function to lable the nodes so that heavy chains have a contigous lable.
- Parameters
-
u | current dfs node |
p | the parent of node u |
- Returns
- void
◆ dfs_par()
Utility function to assign highest parent that can be reached though heavy chains.
- Parameters
-
u | current dfs node |
p | the parent of node u |
- Returns
- 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.
- Returns
- void
460 for (
int i = 0; i < Tree<X>::t_nodes; i++) {
◆ query()
This function returns the sum of node values in the simple path from from node_1 to node_2.
- Parameters
-
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) |
- Returns
- the sum of node values in the simple path from a to b
◆ update()
This function updates the value at node with val.
- Parameters
-
node | the node where the update is done |
val | the value that is being updated |
- Returns
- void
The documentation for this class was generated from the following file:
X chain_query(int a, int b)
Utility function to break down a path query into two chain queries.
Definition: heavy_light_decomposition.cpp:409
std::vector< int > t_size
a vector to store the subtree size rooted at node
Definition: heavy_light_decomposition.cpp:89
int t_root
the root of the tree
Definition: heavy_light_decomposition.cpp:91
int lca(int a, int b)
The function returns the least common ancestor of two nodes.
Definition: heavy_light_decomposition.cpp:229
void init()
This function must be called after the tree adjacency list and node values are populated The function...
Definition: heavy_light_decomposition.cpp:186
void update(int p, X v)
Update the value at a node.
Definition: heavy_light_decomposition.cpp:293
X sret_init
inital query return value
Definition: heavy_light_decomposition.cpp:264
X combine(X lhs, X rhs)
Function that specifies the type of operation involved when segments are combined.
Definition: heavy_light_decomposition.cpp:274
Definition: avltree.cpp:13
void dfs_par(int u, int p=-1)
Utility function to assign highest parent that can be reached though heavy chains.
Definition: heavy_light_decomposition.cpp:371
std::vector< int > h_heavychlid
stores the heavy child of a node
Definition: heavy_light_decomposition.cpp:340
std::vector< std::list< int > > t_adj
an adjacency list to stores the tree edges
Definition: heavy_light_decomposition.cpp:83
std::vector< X > s_tree
Everything here is private, and can only be accessed through the methods, in the derived class (HLD)
Definition: heavy_light_decomposition.cpp:262
const int t_nodes
number of nodes
Definition: heavy_light_decomposition.cpp:84
void dfs_hc(int u, int p=-1)
Utility function to assign heavy child to each node (-1 for a leaf node)
Definition: heavy_light_decomposition.cpp:350
int label
utility member to assign labels in dfs_labels()
Definition: heavy_light_decomposition.cpp:338
std::vector< std::vector< int > > t_par
a matrix to store every node's 2^kth parent
Definition: heavy_light_decomposition.cpp:87
X query(int l, int r)
Make a range query from node label l to node label r.
Definition: heavy_light_decomposition.cpp:305
void dfs_labels(int u, int p=-1)
Utility function to lable the nodes so that heavy chains have a contigous lable.
Definition: heavy_light_decomposition.cpp:390
std::vector< X > t_val
values of nodes
Definition: heavy_light_decomposition.cpp:92
std::vector< int > h_parent
stores the top of the heavy chain from a node
Definition: heavy_light_decomposition.cpp:341
std::vector< int > h_label
stores the label of a node
Definition: heavy_light_decomposition.cpp:339
std::vector< int > t_depth
a vector to store the depth of a node,
Definition: heavy_light_decomposition.cpp:88