range_queries::heavy_light_decomposition::SG< X > Class Template Reference

Segment Tree, to store heavy chains. More...

Inheritance diagram for range_queries::heavy_light_decomposition::SG< X >:

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

Private Member Functions
X	combine (X lhs, X rhs)
	Function that specifies the type of operation involved when segments are combined.
	SG (int size)
	Class parameterized constructor. Resizes the and initilizes the data members.
void	update (int p, X v)
	Update the value at a node.
X	query (int l, int r)
	Make a range query from node label l to node label r.
void	set_sret_init (X new_sret_init)
	Set the initialization for the query data type, based on requirement.

Private Attributes
std::vector< X >	s_tree
	Everything here is private, and can only be accessed through the methods, in the derived class (HLD)
int	s_size
	number of leaves in the segment tree
X	sret_init = 0
	inital query return value

Friends
template<typename T >
class	HLD

Detailed Description

template<typename X>
class range_queries::heavy_light_decomposition::SG< X >

Segment Tree, to store heavy chains.

Template Parameters

the	data type of the values stored in the tree nodes

Constructor & Destructor Documentation

SG()

template<typename X >

range_queries::heavy_light_decomposition::SG< X >::SG ( int size )

inlineexplicitprivate

Class parameterized constructor. Resizes the and initilizes the data members.

Parameters

nodes

the total number of nodes in the tree

Returns

void

                        {
    s_size = size;
    s_tree.assign(2 * s_size, 0ll);
  }

Here is the call graph for this function:

Member Function Documentation

combine()

template<typename X >

X range_queries::heavy_light_decomposition::SG< X >::combine ( X lhs, X rhs )

inlineprivate

Function that specifies the type of operation involved when segments are combined.

Parameters

lhs	the left segment
rhs	the right segment

Returns

the combined result

{ return lhs + rhs; }

query()

template<typename X >

X range_queries::heavy_light_decomposition::SG< X >::query ( int l, int r )

inlineprivate

Make a range query from node label l to node label r.

Parameters

l	node label where the path starts
r	node label where the path ends

Returns

void

                        {
    X lhs = sret_init, rhs = sret_init;
    for (l += s_size, r += s_size + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        lhs = combine(lhs, s_tree[l++]);
      }
      if (r & 1) {
        rhs = combine(s_tree[--r], rhs);
      }
    }
    return combine(lhs, rhs);
  }

Here is the call graph for this function:

set_sret_init()

template<typename X >

void range_queries::heavy_light_decomposition::SG< X >::set_sret_init ( X new_sret_init )

inlineprivate

Set the initialization for the query data type, based on requirement.

Change the sret_init, based on requirement:

• Sum Query: 0 (Default)
• XOR Query: 0 (Default)
• Min Query: Infinity
• Max Query: -Infinity

  Parameters

  new_sret_init

  the new init

{ sret_init = new_sret_init; }

update()

template<typename X >

void range_queries::heavy_light_decomposition::SG< X >::update ( int p, X v )

inlineprivate

Update the value at a node.

Parameters

p	the node to be udpated
v	the update value

Returns

void

                          {
    for (p += s_size; p > 0; p >>= 1) {
      s_tree[p] += v;
    }
  }

Member Data Documentation

s_tree

template<typename X >

std::vector<X> range_queries::heavy_light_decomposition::SG< X >::s_tree

private

Everything here is private, and can only be accessed through the methods, in the derived class (HLD)

the segment tree, stored as a vector

---

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

• range_queries/heavy_light_decomposition.cpp