Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
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. | |
class representation of the segment tree
T | The type of the class that goes in the datastructure |
|
inline |
|
inlineprivate |
Any associative function that combines x and y.
x | The first operand |
y | The second operand |
|
inlineprivate |
Gives the midpoint between two integers.
l | The left endpoint |
r | The right endpoint |
|
inlineprivate |
Helper method for range_comb method below.
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 |
|
inline |
Returns comb across all values between l and r.
l | The left endpoint of the range |
r | The right endpoint of the range |
|
inlineprivate |
Helper method for update method below.
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 |
|
inline |