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

Definition at line 254 of file heavy_light_decomposition.cpp.

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

Definition at line 282 of file heavy_light_decomposition.cpp.

                        {
    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

Definition at line 274 of file heavy_light_decomposition.cpp.

{ 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

Definition at line 305 of file heavy_light_decomposition.cpp.

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

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

Definition at line 329 of file heavy_light_decomposition.cpp.

{ 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

Definition at line 293 of file heavy_light_decomposition.cpp.

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

Friends And Related Symbol Documentation

HLD

template<typename X >

template<typename T >

friend class HLD

friend

Definition at line 265 of file heavy_light_decomposition.cpp.

Member Data Documentation

s_size

template<typename X >

int range_queries::heavy_light_decomposition::SG< X >::s_size

private

number of leaves in the segment tree

Definition at line 263 of file heavy_light_decomposition.cpp.

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

Definition at line 262 of file heavy_light_decomposition.cpp.

sret_init

template<typename X >

X range_queries::heavy_light_decomposition::SG< X >::sret_init = 0

private

inital query return value

Definition at line 264 of file heavy_light_decomposition.cpp.

---

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

• range_queries/heavy_light_decomposition.cpp