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

Definition at line 78 of file heavy_light_decomposition.cpp.

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

Definition at line 140 of file heavy_light_decomposition.cpp.

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

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

Definition at line 157 of file heavy_light_decomposition.cpp.

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

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

Definition at line 167 of file heavy_light_decomposition.cpp.

{ 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

Definition at line 116 of file heavy_light_decomposition.cpp.

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

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

Definition at line 101 of file heavy_light_decomposition.cpp.

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

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

Definition at line 186 of file heavy_light_decomposition.cpp.

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

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

Definition at line 218 of file heavy_light_decomposition.cpp.

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

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

Definition at line 229 of file heavy_light_decomposition.cpp.

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

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

Definition at line 200 of file heavy_light_decomposition.cpp.

                                    {
    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

Definition at line 175 of file heavy_light_decomposition.cpp.

                                                  {
    assert(static_cast<int>(node_val.size()) == t_nodes);
    t_val = node_val;
  }

Friends And Related Symbol Documentation

HLD

template<typename X >

template<typename T >

friend class HLD

friend

Definition at line 93 of file heavy_light_decomposition.cpp.

Member Data Documentation

t_adj

template<typename X >

std::vector<std::list<int> > range_queries::heavy_light_decomposition::Tree< X >::t_adj

private

an adjacency list to stores the tree edges

Definition at line 83 of file heavy_light_decomposition.cpp.

t_depth

template<typename X >

std::vector<int> range_queries::heavy_light_decomposition::Tree< X >::t_depth

private

a vector to store the depth of a node,

Definition at line 88 of file heavy_light_decomposition.cpp.

t_maxlift

template<typename X >

const int range_queries::heavy_light_decomposition::Tree< X >::t_maxlift

private

maximum possible height of the tree

Definition at line 85 of file heavy_light_decomposition.cpp.

t_nodes

template<typename X >

const int range_queries::heavy_light_decomposition::Tree< X >::t_nodes

private

number of nodes

Definition at line 84 of file heavy_light_decomposition.cpp.

t_par

template<typename X >

std::vector<std::vector<int> > range_queries::heavy_light_decomposition::Tree< X >::t_par

private

a matrix to store every node's 2^kth parent

Definition at line 87 of file heavy_light_decomposition.cpp.

t_root

template<typename X >

int range_queries::heavy_light_decomposition::Tree< X >::t_root

private

the root of the tree

Definition at line 91 of file heavy_light_decomposition.cpp.

t_size

template<typename X >

std::vector<int> range_queries::heavy_light_decomposition::Tree< X >::t_size

private

a vector to store the subtree size rooted at node

Definition at line 89 of file heavy_light_decomposition.cpp.

t_val

template<typename X >

std::vector<X> range_queries::heavy_light_decomposition::Tree< X >::t_val

private

values of nodes

Definition at line 92 of file heavy_light_decomposition.cpp.

---

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

• range_queries/heavy_light_decomposition.cpp