data_structures::SegmentTree< T > Class Template Reference

class representation of the segment tree More...

Public Member Functions
	SegmentTree (int n)
void	update (int pos, T val)
	Updates a value at a certain position.
T	range_comb (int l, int r)
	Returns comb across all values between l and r.

Private Member Functions
T	comb (T x, T y)
	Any associative function that combines x and y.
int	mid (int l, int r)
	Gives the midpoint between two integers.
void	update (int i, int l, int r, int pos, T val)
	Helper method for update method below.
T	range_comb (int i, int l, int r, int tl, int tr)
	Helper method for range_comb method below.

Private Attributes
const T	ID = 0
	Comb(ID, x) = x.
std::vector< T >	t
	Vector to represent the tree.
int	size = 0
	Number of elements available for querying in the tree.

Detailed Description

template<class T>
class data_structures::SegmentTree< T >

class representation of the segment tree

Template Parameters

T	The type of the class that goes in the datastructure

Definition at line 30 of file segment_tree.cpp.

Constructor & Destructor Documentation

SegmentTree()

template<class T>

data_structures::SegmentTree< T >::SegmentTree ( int n )

inline

Definition at line 87 of file segment_tree.cpp.

: t(n * 4, ID), size(n) {}

Member Function Documentation

comb()

template<class T>

T data_structures::SegmentTree< T >::comb ( T x, T y )

inlineprivate

Any associative function that combines x and y.

Parameters

x	The first operand
y	The second operand

Returns

Some associative operation applied to these two values. In this case, I used addition

Definition at line 42 of file segment_tree.cpp.

                     {
        return x + y;
    }

mid()

template<class T>

int data_structures::SegmentTree< T >::mid ( int l, int r )

inlineprivate

Gives the midpoint between two integers.

Parameters

l	The left endpoint
r	The right endpoint

Returns

the middle point between them

Definition at line 51 of file segment_tree.cpp.

                          {
        return l + (r - l) / 2;
    }

range_comb() [1/2]

template<class T>

T data_structures::SegmentTree< T >::range_comb ( int i, int l, int r, int tl, int tr )

inlineprivate

Helper method for range_comb method below.

Parameters

i	The current node
l	The leftmost node of the current node
r	The rightmost node of the current node
tl	The left endpoint of the range
tr	The right endpoint of the range

Returns

The comb operation applied to all values between tl and tr

Definition at line 80 of file segment_tree.cpp.

                                                      {
        if(l == tl && r == tr) return t[i];
        if(tl > tr) return 0;
        int m = mid(l, r);
        return comb(range_comb(i * 2, l, m, tl, std::min(tr, m)), range_comb(i * 2 + 1, m + 1, r, std::max(tl, m + 1), tr));
    }

range_comb() [2/2]

template<class T>

T data_structures::SegmentTree< T >::range_comb ( int l, int r )

inline

Returns comb across all values between l and r.

Parameters

l	The left endpoint of the range
r	The right endpoint of the range

Returns

The value of the comb operations

Definition at line 102 of file segment_tree.cpp.

                               {
        return range_comb(1, 1, size, l, r);
    }

update() [1/2]

template<class T>

void data_structures::SegmentTree< T >::update ( int i, int l, int r, int pos, T val )

inlineprivate

Helper method for update method below.

Parameters

i	The index of the current node
l	The leftmost node of the current node
r	The rightmost node of the current node
pos	The position to update
val	The value to update it to

Definition at line 62 of file segment_tree.cpp.

                                                     {
        if(l == r) t[i] = val;
        else {
            int m = mid(l, r);
            if(pos <= m) update(i * 2, l, m, pos, val);
            else update(i * 2 + 1, m + 1, r, pos, val);
            t[i] = comb(t[i * 2], t[i * 2 + 1]);
        }
    }

update() [2/2]

template<class T>

void data_structures::SegmentTree< T >::update ( int pos, T val )

inline

Updates a value at a certain position.

Parameters

pos	The position to update
val	The value to update it to

Definition at line 93 of file segment_tree.cpp.

                                {
        update(1, 1, size, pos, val);
    }

Member Data Documentation

ID

template<class T>

const T data_structures::SegmentTree< T >::ID = 0

private

Comb(ID, x) = x.

Definition at line 32 of file segment_tree.cpp.

size

template<class T>

int data_structures::SegmentTree< T >::size = 0

private

Number of elements available for querying in the tree.

Definition at line 34 of file segment_tree.cpp.

t

template<class T>

std::vector<T> data_structures::SegmentTree< T >::t

private

Vector to represent the tree.

Definition at line 33 of file segment_tree.cpp.

---

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

• data_structures/segment_tree.cpp