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. More...
	SG (int size)
	Class parameterized constructor. Resizes the and initilizes the data members. More...
void	update (int p, X v)
	Update the value at a node. More...
X	query (int l, int r)
	Make a range query from node label l to node label r. More...
void	set_sret_init (X new_sret_init)
	Set the initialization for the query data type, based on requirement. More...

Private Attributes
std::vector< X >	s_tree
	Everything here is private, and can only be accessed through the methods, in the derived class (HLD) More...
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);
  }

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