Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
range_queries::heavy_light_decomposition::Tree< X > Class Template Reference

A Basic Tree, which supports binary lifting. More...

Inheritance diagram for range_queries::heavy_light_decomposition::Tree< X >:
[legend]
Collaboration diagram for range_queries::heavy_light_decomposition::Tree< X >:
[legend]

Public Member Functions

 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...
 

Private Member Functions

void dfs_size (int u, int p=-1)
 Utility function to compute sub-tree sizes. More...
 
void dfs_lca (int u, int p=-1)
 Utility function to populate the t_par vector. More...
 

Private Attributes

std::vector< std::list< int > > t_adj
 an adjacency list to stores the tree edges
 
const int t_nodes
 number of nodes
 
const int t_maxlift
 maximum possible height of the tree
 
std::vector< std::vector< int > > t_par
 a matrix to store every node's 2^kth parent
 
std::vector< int > t_depth
 a vector to store the depth of a node,
 
std::vector< int > t_size
 a vector to store the subtree size rooted at node
 
int t_root
 the root of the tree
 
std::vector< X > t_val
 values of nodes
 

Friends

template<typename T >
class HLD
 

Detailed Description

template<typename X>
class range_queries::heavy_light_decomposition::Tree< X >

A Basic Tree, which supports binary lifting.

Template Parameters
thedata type of the values stored in the tree nodes Deleting the default constructor An instance can only be created with the number of nodes Defaults: t_node indexing are zero based t_root is 0 depth of root_node is 0 Supports: lift :- lift a node k units up the tree kth_ancestor :- returns the kth ancestor lca :- returns the least common ancestor

Constructor & Destructor Documentation

◆ Tree()

template<typename X >
range_queries::heavy_light_decomposition::Tree< X >::Tree ( int  nodes)
inlineexplicit

Class parameterized constructor, resizes the and initializes the data members.

Parameters
nodesthe total number of nodes in the tree
141  : t_nodes(nodes), t_maxlift(static_cast<int>(floor(log2(nodes))) + 1) {
142  /* Initialize and resize all the vectors */
143  t_root = 0; /* Default */
146  t_depth.assign(t_nodes, 0);
147  t_size.assign(t_nodes, 1);
149  }
Here is the call graph for this function:

Member Function Documentation

◆ add_edge()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::add_edge ( const int  u,
const int  v 
)
inline

Adds an undirected edge from node u to node v in the tree.

Parameters
uthe node where the edge is from
vthe node where the edge is to
Returns
void
157  {
158  t_adj[u].push_back(v);
159  t_adj[v].push_back(u);
160  }
Here is the call graph for this function:

◆ change_root()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::change_root ( int  new_root)
inline

Set the root for the tree.

Parameters
new_rootthe new root
Returns
void
167 { t_root = new_root; }

◆ dfs_lca()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::dfs_lca ( int  u,
int  p = -1 
)
inlineprivate

Utility function to populate the t_par vector.

Parameters
ucurrent dfs node
pthe parent of node u
Returns
void
116  {
117  t_par[u][0] = p;
118  if (p != -1) {
119  t_depth[u] = 1 + t_depth[p];
120  }
121  for (int k = 1; k < t_maxlift; k++) {
122  if (t_par[u][k - 1] != -1) {
123  t_par[u][k] = t_par[t_par[u][k - 1]][k - 1];
124  }
125  }
126 
127  for (const int &v : t_adj[u]) {
128  if (v ^ p) {
129  dfs_lca(v, u);
130  }
131  }
132  }

◆ dfs_size()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::dfs_size ( int  u,
int  p = -1 
)
inlineprivate

Utility function to compute sub-tree sizes.

Parameters
ucurrent dfs node
pthe parent of node
u
Returns
void
101  {
102  for (const int &v : t_adj[u]) {
103  if (v ^ p) {
104  dfs_size(v, u);
105  t_size[u] += t_size[v];
106  }
107  }
108  }

◆ init()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::init ( )
inline

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.

Returns
void
186  {
187  assert(t_nodes > 0);
188  dfs_size(t_root);
189  dfs_lca(t_root);
190  }
Here is the call graph for this function:

◆ kth_ancestor()

template<typename X >
int range_queries::heavy_light_decomposition::Tree< X >::kth_ancestor ( int  p,
const int &  dist 
)
inline

The function returns the kth ancestor of a node.

Parameters
pthe node id whose kth ancestor is to be found
distthe distance to move up the tree
Returns
the kth ancestor of node
218  {
219  lift(&p, dist);
220  return p;
221  }
Here is the call graph for this function:

◆ lca()

template<typename X >
int range_queries::heavy_light_decomposition::Tree< X >::lca ( int  a,
int  b 
)
inline

The function returns the least common ancestor of two nodes.

Parameters
anode id_1
bnode id_2
Returns
the least common ancestor of node a, and node b
229  {
230  assert(a >= 0 and b >= 0 and a < t_nodes and b < t_nodes);
231  if (t_depth[a] > t_depth[b]) {
232  lift(&a, t_depth[a] - t_depth[b]);
233  }
234  if (t_depth[b] > t_depth[a]) {
235  lift(&b, t_depth[b] - t_depth[a]);
236  }
237  if (a == b) {
238  return a;
239  }
240  for (int k = t_maxlift - 1; k >= 0; k--) {
241  if (t_par[a][k] != t_par[b][k]) {
242  a = t_par[a][k];
243  b = t_par[b][k];
244  }
245  }
246  return t_par[a][0];
247  }
Here is the call graph for this function:

◆ lift()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::lift ( int *const  p,
int  dist 
)
inline

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.

Parameters
pa pointer to the variable that stores the node id
distthe distance to move up the tree
Returns
void
200  {
201  for (int k = 0; k < t_maxlift; k++) {
202  if (*p == -1) {
203  return;
204  }
205  if (dist & 1) {
206  *p = t_par[*p][k];
207  }
208  dist >>= 1;
209  }
210  }

◆ set_node_val()

template<typename X >
void range_queries::heavy_light_decomposition::Tree< X >::set_node_val ( const std::vector< X > &  node_val)
inline

Set the values for all the nodes.

Parameters
node_vala vector of size n, with all the node values where, n is the number of nodes
Returns
void
175  {
176  assert(static_cast<int>(node_val.size()) == t_nodes);
177  t_val = node_val;
178  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
std::vector::resize
T resize(T... args)
std::floor
T floor(T... args)
range_queries::heavy_light_decomposition::Tree::t_size
std::vector< int > t_size
a vector to store the subtree size rooted at node
Definition: heavy_light_decomposition.cpp:89
range_queries::heavy_light_decomposition::Tree::dfs_lca
void dfs_lca(int u, int p=-1)
Utility function to populate the t_par vector.
Definition: heavy_light_decomposition.cpp:116
range_queries::heavy_light_decomposition::Tree::t_root
int t_root
the root of the tree
Definition: heavy_light_decomposition.cpp:91
range_queries::heavy_light_decomposition::Tree::t_maxlift
const int t_maxlift
maximum possible height of the tree
Definition: heavy_light_decomposition.cpp:85
std::vector< int >
std::vector::size
T size(T... args)
range_queries::heavy_light_decomposition::Tree::lift
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 store...
Definition: heavy_light_decomposition.cpp:200
std::vector::push_back
T push_back(T... args)
range_queries::heavy_light_decomposition::Tree::t_adj
std::vector< std::list< int > > t_adj
an adjacency list to stores the tree edges
Definition: heavy_light_decomposition.cpp:83
range_queries::heavy_light_decomposition::Tree::t_nodes
const int t_nodes
number of nodes
Definition: heavy_light_decomposition.cpp:84
range_queries::heavy_light_decomposition::Tree::t_par
std::vector< std::vector< int > > t_par
a matrix to store every node's 2^kth parent
Definition: heavy_light_decomposition.cpp:87
range_queries::heavy_light_decomposition::Tree::t_val
std::vector< X > t_val
values of nodes
Definition: heavy_light_decomposition.cpp:92
std::vector::assign
T assign(T... args)
range_queries::heavy_light_decomposition::Tree::dfs_size
void dfs_size(int u, int p=-1)
Utility function to compute sub-tree sizes.
Definition: heavy_light_decomposition.cpp:101
range_queries::heavy_light_decomposition::Tree::t_depth
std::vector< int > t_depth
a vector to store the depth of a node,
Definition: heavy_light_decomposition.cpp:88