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

Definition at line 336 of file heavy_light_decomposition.cpp.

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

Definition at line 409 of file heavy_light_decomposition.cpp.

                             : 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

Definition at line 409 of file heavy_light_decomposition.cpp.

                              {
    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;
  }

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

Definition at line 350 of file heavy_light_decomposition.cpp.

                                 {
    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;
  }

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

Definition at line 390 of file heavy_light_decomposition.cpp.

                                     {
    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);
      }
    }
  }

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

Definition at line 371 of file heavy_light_decomposition.cpp.

                                  {
    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);
      }
    }
  }

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

Definition at line 450 of file heavy_light_decomposition.cpp.

              {
    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]);
    }
  }

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

Definition at line 489 of file heavy_light_decomposition.cpp.

                        {
    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];
  }

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

Definition at line 475 of file heavy_light_decomposition.cpp.

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

Member Data Documentation

h_heavychlid

template<typename X >

std::vector<int> range_queries::heavy_light_decomposition::HLD< X >::h_heavychlid

private

stores the heavy child of a node

Definition at line 340 of file heavy_light_decomposition.cpp.

h_label

template<typename X >

std::vector<int> range_queries::heavy_light_decomposition::HLD< X >::h_label

private

stores the label of a node

Definition at line 339 of file heavy_light_decomposition.cpp.

h_parent

template<typename X >

std::vector<int> range_queries::heavy_light_decomposition::HLD< X >::h_parent

private

stores the top of the heavy chain from a node

Definition at line 341 of file heavy_light_decomposition.cpp.

label

template<typename X >

int range_queries::heavy_light_decomposition::HLD< X >::label

private

utility member to assign labels in dfs_labels()

Definition at line 338 of file heavy_light_decomposition.cpp.

---

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

• range_queries/heavy_light_decomposition.cpp