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

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

Public Member Functions
	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_size (int u, int p=-1)
	Utility function to compute sub-tree sizes.
void	dfs_lca (int u, int p=-1)
	Utility function to populate the t_par vector.

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

the	data 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

nodes

the total number of nodes in the tree

      : t_nodes(nodes), t_maxlift(static_cast<int>(floor(log2(nodes))) + 1) {
    /* Initialize and resize all the vectors */
    t_root = 0; /* Default */
    t_adj.resize(t_nodes);
    t_par.assign(t_nodes, std::vector<int>(t_maxlift, -1));
    t_depth.assign(t_nodes, 0);
    t_size.assign(t_nodes, 1);
    t_val.resize(t_nodes);
  }

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

u	the node where the edge is from
v	the node where the edge is to

Returns

void

                                          {
    t_adj[u].push_back(v);
    t_adj[v].push_back(u);
  }

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_root

the new root

Returns

void

{ 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

u	current dfs node
p	the parent of node u

Returns

void

                                  {
    t_par[u][0] = p;
    if (p != -1) {
      t_depth[u] = 1 + t_depth[p];
    }
    for (int k = 1; k < t_maxlift; k++) {
      if (t_par[u][k - 1] != -1) {
        t_par[u][k] = t_par[t_par[u][k - 1]][k - 1];
      }
    }
 
    for (const int &v : t_adj[u]) {
      if (v ^ p) {
        dfs_lca(v, u);
      }
    }
  }

Here is the call graph for this function:

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

u	current dfs node
p	the parent of node
u

Returns

void

                                   {
    for (const int &v : t_adj[u]) {
      if (v ^ p) {
        dfs_size(v, u);
        t_size[u] += t_size[v];
      }
    }
  }

Here is the call graph for this function:

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

              {
    assert(t_nodes > 0);
    dfs_size(t_root);
    dfs_lca(t_root);
  }

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

p	the node id whose kth ancestor is to be found
dist	the distance to move up the tree

Returns

the kth ancestor of node

                                           {
    lift(&p, dist);
    return p;
  }

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

a	node id_1
b	node id_2

Returns

the least common ancestor of node a, and node b

                        {
    assert(a >= 0 and b >= 0 and a < t_nodes and b < t_nodes);
    if (t_depth[a] > t_depth[b]) {
      lift(&a, t_depth[a] - t_depth[b]);
    }
    if (t_depth[b] > t_depth[a]) {
      lift(&b, t_depth[b] - t_depth[a]);
    }
    if (a == b) {
      return a;
    }
    for (int k = t_maxlift - 1; k >= 0; k--) {
      if (t_par[a][k] != t_par[b][k]) {
        a = t_par[a][k];
        b = t_par[b][k];
      }
    }
    return t_par[a][0];
  }

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

p	a pointer to the variable that stores the node id
dist	the distance to move up the tree

Returns

void

                                    {
    for (int k = 0; k < t_maxlift; k++) {
      if (*p == -1) {
        return;
      }
      if (dist & 1) {
        *p = t_par[*p][k];
      }
      dist >>= 1;
    }
  }

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_val

a vector of size n, with all the node values where, n is the number of nodes

Returns

void

                                                  {
    assert(static_cast<int>(node_val.size()) == t_nodes);
    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