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

Collaboration diagram for range_queries::heavy_light_decomposition::HLD< X >:

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

Detailed Description

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

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

nodes

the total number of nodes in the tree

                             : Tree<X>(nodes), SG<X>(nodes) {
    /* Initialization and resize vectors */
    label = 0;
    h_label.assign(Tree<X>::t_nodes, -1);
    h_heavychlid.assign(Tree<X>::t_nodes, -1);
    h_parent.resize(Tree<X>::t_nodes);
    iota(h_parent.begin(), h_parent.end(), 0);
  }

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

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

                              {
    X ret = SG<X>::sret_init;
    if (Tree<X>::t_depth[a] < Tree<X>::t_depth[b]) {
      std::swap(a, b);
    }
    while (Tree<X>::t_depth[a] >= Tree<X>::t_depth[b]) {
      int l = h_label[h_parent[a]];
      int r = h_label[a];
      if (Tree<X>::t_depth[h_parent[a]] < Tree<X>::t_depth[b]) {
        l += Tree<X>::t_depth[b] - Tree<X>::t_depth[h_parent[a]];
      }
      ret = SG<X>::combine(ret, SG<X>::query(l, r));
      a = Tree<X>::t_par[h_parent[a]][0];
      if (a == -1) {
        break;
      }
    }
    return ret;
  }

Here is the call graph for this function:

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

u	current dfs node
p	the parent of node u

Returns

void

                                 {
    int hc_size = -1, hc_id = -1;
    for (const int &v : Tree<X>::t_adj[u]) {
      if (v ^ p) {
        dfs_hc(v, u);
        if (Tree<X>::t_size[v] > hc_size) {
          hc_size = Tree<X>::t_size[v];
          hc_id = v;
        }
      }
    }
    h_heavychlid[u] = hc_id;
  }

Here is the call graph for this function:

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

u	current dfs node
p	the parent of node u

Returns

void

                                     {
    h_label[u] = label++;
    if (h_heavychlid[u] != -1) {
      dfs_labels(h_heavychlid[u], u);
    }
    for (const int &v : Tree<X>::t_adj[u]) {
      if (v ^ p and v ^ h_heavychlid[u]) {
        dfs_labels(v, u);
      }
    }
  }

Here is the call graph for this function:

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

u	current dfs node
p	the parent of node u

Returns

void

                                  {
    if (h_heavychlid[u] != -1) {
      h_parent[h_heavychlid[u]] = h_parent[u];
      dfs_par(h_heavychlid[u], u);
    }
    for (const int &v : Tree<X>::t_adj[u]) {
      if (v ^ p and v ^ h_heavychlid[u]) {
        dfs_par(v, u);
      }
    }
  }

Here is the call graph for this function:

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

              {
    Tree<X>::init();
 
    // Fill the heavy child, greatest parent, and labels
    label = 0;
    dfs_hc(Tree<X>::t_root);
    dfs_par(Tree<X>::t_root);
    dfs_labels(Tree<X>::t_root);
 
    // Segment Tree Initialization
    for (int i = 0; i < Tree<X>::t_nodes; i++) {
      SG<X>::s_tree[h_label[i] + Tree<X>::t_nodes] = Tree<X>::t_val[i];
    }
    for (int i = Tree<X>::t_nodes - 1; i > 0; i--) {
      SG<X>::s_tree[i] =
          SG<X>::combine(SG<X>::s_tree[i << 1], SG<X>::s_tree[i << 1 | 1]);
    }
  }

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

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

                        {
    int lc = Tree<X>::lca(a, b);
    X ret = SG<X>::sret_init;
    assert(lc != -1);
    ret += chain_query(a, lc);
    ret += chain_query(b, lc);
    return ret - Tree<X>::t_val[lc];
  }

Here is the call graph for this function:

update()

template<typename X >

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

inline

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

                               {
    X diff = val - Tree<X>::t_val[node];
    SG<X>::update(h_label[node], diff);
    Tree<X>::t_val[node] = val;
  }

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• range_queries/heavy_light_decomposition.cpp