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

The Heavy-Light Decomposition class. More...

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

Public Member Functions

 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...
 
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...
 
- 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. 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_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...
 
chain_query (int a, int b)
 Utility function to break down a path query into two chain queries. More...
 

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
 

Detailed Description

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

The Heavy-Light Decomposition class.

Template Parameters
thedata type of the values stored in the tree nodes

Constructor & Destructor Documentation

◆ HLD()

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

Class parameterized constructor. Resizes the and initilizes the data members.

Parameters
nodesthe total number of nodes in the tree
435  : Tree<X>(nodes), SG<X>(nodes) {
436  /* Initialization and resize vectors */
437  label = 0;
441  iota(h_parent.begin(), h_parent.end(), 0);
442  }
Here is the call graph for this function:

Member Function Documentation

◆ chain_query()

template<typename X >
X range_queries::heavy_light_decomposition::HLD< X >::chain_query ( int  a,
int  b 
)
inlineprivate

Utility function to break down a path query into two chain queries.

Parameters
anode where the path starts
bnode 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
409  {
410  X ret = SG<X>::sret_init;
411  if (Tree<X>::t_depth[a] < Tree<X>::t_depth[b]) {
412  std::swap(a, b);
413  }
414  while (Tree<X>::t_depth[a] >= Tree<X>::t_depth[b]) {
415  int l = h_label[h_parent[a]];
416  int r = h_label[a];
419  }
420  ret = SG<X>::combine(ret, SG<X>::query(l, r));
421  a = Tree<X>::t_par[h_parent[a]][0];
422  if (a == -1) {
423  break;
424  }
425  }
426  return ret;
427  }

◆ dfs_hc()

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

Utility function to assign heavy child to each node (-1 for a leaf node)

Parameters
ucurrent dfs node
pthe parent of node u
Returns
void
350  {
351  int hc_size = -1, hc_id = -1;
352  for (const int &v : Tree<X>::t_adj[u]) {
353  if (v ^ p) {
354  dfs_hc(v, u);
355  if (Tree<X>::t_size[v] > hc_size) {
356  hc_size = Tree<X>::t_size[v];
357  hc_id = v;
358  }
359  }
360  }
361  h_heavychlid[u] = hc_id;
362  }

◆ dfs_labels()

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

Utility function to lable the nodes so that heavy chains have a contigous lable.

Parameters
ucurrent dfs node
pthe parent of node u
Returns
void
390  {
391  h_label[u] = label++;
392  if (h_heavychlid[u] != -1) {
393  dfs_labels(h_heavychlid[u], u);
394  }
395  for (const int &v : Tree<X>::t_adj[u]) {
396  if (v ^ p and v ^ h_heavychlid[u]) {
397  dfs_labels(v, u);
398  }
399  }
400  }

◆ dfs_par()

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

Utility function to assign highest parent that can be reached though heavy chains.

Parameters
ucurrent dfs node
pthe parent of node u
Returns
void
371  {
372  if (h_heavychlid[u] != -1) {
373  h_parent[h_heavychlid[u]] = h_parent[u];
374  dfs_par(h_heavychlid[u], u);
375  }
376  for (const int &v : Tree<X>::t_adj[u]) {
377  if (v ^ p and v ^ h_heavychlid[u]) {
378  dfs_par(v, u);
379  }
380  }
381  }

◆ init()

template<typename X >
void range_queries::heavy_light_decomposition::HLD< X >::init ( )
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.

Returns
void
450  {
451  Tree<X>::init();
452 
453  // Fill the heavy child, greatest parent, and labels
454  label = 0;
458 
459  // Segment Tree Initialization
460  for (int i = 0; i < Tree<X>::t_nodes; i++) {
462  }
463  for (int i = Tree<X>::t_nodes - 1; i > 0; i--) {
464  SG<X>::s_tree[i] =
465  SG<X>::combine(SG<X>::s_tree[i << 1], SG<X>::s_tree[i << 1 | 1]);
466  }
467  }
Here is the call graph for this function:

◆ query()

template<typename X >
X range_queries::heavy_light_decomposition::HLD< X >::query ( int  a,
int  b 
)
inline

This function returns the sum of node values in the simple path from from node_1 to node_2.

Parameters
athe node where the simple path starts
bthe 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
489  {
490  int lc = Tree<X>::lca(a, b);
491  X ret = SG<X>::sret_init;
492  assert(lc != -1);
493  ret += chain_query(a, lc);
494  ret += chain_query(b, lc);
495  return ret - Tree<X>::t_val[lc];
496  }
Here is the call graph for this function:

◆ update()

template<typename X >
void range_queries::heavy_light_decomposition::HLD< X >::update ( int  node,
val 
)
inline

This function updates the value at node with val.

Parameters
nodethe node where the update is done
valthe value that is being updated
Returns
void
475  {
476  X diff = val - Tree<X>::t_val[node];
477  SG<X>::update(h_label[node], diff);
478  Tree<X>::t_val[node] = val;
479  }
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)
range_queries::heavy_light_decomposition::HLD::chain_query
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
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::t_root
int t_root
the root of the tree
Definition: heavy_light_decomposition.cpp:91
range_queries::heavy_light_decomposition::Tree::lca
int lca(int a, int b)
The function returns the least common ancestor of two nodes.
Definition: heavy_light_decomposition.cpp:229
range_queries::heavy_light_decomposition::Tree::init
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
range_queries::heavy_light_decomposition::SG::update
void update(int p, X v)
Update the value at a node.
Definition: heavy_light_decomposition.cpp:293
range_queries::heavy_light_decomposition::SG::sret_init
X sret_init
inital query return value
Definition: heavy_light_decomposition.cpp:264
range_queries::heavy_light_decomposition::SG::combine
X combine(X lhs, X rhs)
Function that specifies the type of operation involved when segments are combined.
Definition: heavy_light_decomposition.cpp:274
node
Definition: avltree.cpp:13
node
struct list node
range_queries::heavy_light_decomposition::HLD::dfs_par
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
range_queries::heavy_light_decomposition::HLD::h_heavychlid
std::vector< int > h_heavychlid
stores the heavy child of a node
Definition: heavy_light_decomposition.cpp:340
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::SG::s_tree
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
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::HLD::dfs_hc
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
range_queries::heavy_light_decomposition::HLD::label
int label
utility member to assign labels in dfs_labels()
Definition: heavy_light_decomposition.cpp:338
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
std::swap
T swap(T... args)
range_queries::heavy_light_decomposition::SG::query
X query(int l, int r)
Make a range query from node label l to node label r.
Definition: heavy_light_decomposition.cpp:305
range_queries::heavy_light_decomposition::HLD::dfs_labels
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
range_queries::heavy_light_decomposition::Tree::t_val
std::vector< X > t_val
values of nodes
Definition: heavy_light_decomposition.cpp:92
std::vector::begin
T begin(T... args)
std::iota
T iota(T... args)
range_queries::heavy_light_decomposition::HLD::h_parent
std::vector< int > h_parent
stores the top of the heavy chain from a node
Definition: heavy_light_decomposition.cpp:341
std::vector::assign
T assign(T... args)
std::vector::end
T end(T... args)
range_queries::heavy_light_decomposition::HLD::h_label
std::vector< int > h_label
stores the label of a node
Definition: heavy_light_decomposition.cpp:339
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