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 342 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 441 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 415 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 356 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 396 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 377 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 456 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 495 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 481 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;
    }