Range query here is range sum, but the code can be modified to make different queries like range max or min.
More...
|
void | construct (const std::vector< int64_t > &vec) |
| Constructing the segment tree with the values in the passed vector. Returned root pointer is pushed in the pointers vector to have access to the original version if the segment tree is updated.
|
|
void | update (const uint32_t &l, const uint32_t &r, const int64_t &value) |
| Doing range update by passing the left and right indexes of the range as well as the value to be added.
|
|
int64_t | query (const uint32_t &l, const uint32_t &r, const uint32_t &version) |
| Querying the range from index l to index r, getting the sum of the elements whose index x satisfies l<=x<=r.
|
|
uint32_t | size () |
| Getting the number of versions after updates so far which is equal to the size of the pointers vector.
|
|
|
std::shared_ptr< Node > | newKid (std::shared_ptr< Node > const &curr) |
| Creating a new node with the same values of curr node.
|
|
void | lazy (const uint32_t &i, const uint32_t &j, std::shared_ptr< Node > const &curr) |
| If there is some value to be propagated to the passed node, value is added to the node and the children of the node, if exist, are copied and the propagated value is also added to them.
|
|
std::shared_ptr< Node > | construct (const uint32_t &i, const uint32_t &j) |
| Constructing the segment tree with the early passed vector. Every call creates a node to hold the sum of the given range, set its pointers to the children, and set its value to the sum of the children's values.
|
|
std::shared_ptr< Node > | update (const uint32_t &i, const uint32_t &j, const uint32_t &l, const uint32_t &r, const int64_t &value, std::shared_ptr< Node > const &curr) |
| Doing range update, checking at every node if it has some value to be propagated. All nodes affected by the update are copied and propagation value is added to the leaf of them.
|
|
int64_t | query (const uint32_t &i, const uint32_t &j, const uint32_t &l, const uint32_t &r, std::shared_ptr< Node > const &curr) |
| Querying the range from index l to index r, checking at every node if it has some value to be propagated. Current node's value is returned if its range is completely inside the wanted range, else 0 is returned.
|
|
Range query here is range sum, but the code can be modified to make different queries like range max or min.
◆ construct() [1/2]
void range_queries::perSegTree::construct |
( |
const std::vector< int64_t > & | vec | ) |
|
|
inline |
Constructing the segment tree with the values in the passed vector. Returned root pointer is pushed in the pointers vector to have access to the original version if the segment tree is updated.
public methods that can be used directly from outside the class. They call the private functions that do all the work
- Parameters
-
vec | vector whose values will be used to build the segment tree |
- Returns
- void
200 {
202 return;
203 }
208 }
std::vector< std::shared_ptr< Node > > ptrs
number of elements/leaf nodes in the segment tree
Definition persistent_seg_tree_lazy_prop.cpp:54
std::shared_ptr< Node > construct(const uint32_t &i, const uint32_t &j)
Constructing the segment tree with the early passed vector. Every call creates a node to hold the sum...
Definition persistent_seg_tree_lazy_prop.cpp:106
std::vector< int64_t > vec
Definition persistent_seg_tree_lazy_prop.cpp:57
◆ construct() [2/2]
std::shared_ptr< Node > range_queries::perSegTree::construct |
( |
const uint32_t & | i, |
|
|
const uint32_t & | j ) |
|
inlineprivate |
Constructing the segment tree with the early passed vector. Every call creates a node to hold the sum of the given range, set its pointers to the children, and set its value to the sum of the children's values.
- Parameters
-
i | the left index of the range that the created node holds its sum |
j | the right index of the range that the created node holds its sum |
- Returns
- pointer to the newly created node
106 {
108 if (i == j) {
109 newNode->val =
vec[i];
110 } else {
111 uint32_t mid = i + (j - i) / 2;
114 newNode->val = leftt->val +
right->val;
115 newNode->left = leftt;
116 newNode->right =
right;
117 }
118 return newNode;
119 }
Definition linkedlist_implentation_usingarray.cpp:14
◆ lazy()
void range_queries::perSegTree::lazy |
( |
const uint32_t & | i, |
|
|
const uint32_t & | j, |
|
|
std::shared_ptr< Node > const & | curr ) |
|
inlineprivate |
If there is some value to be propagated to the passed node, value is added to the node and the children of the node, if exist, are copied and the propagated value is also added to them.
- Parameters
-
i | the left index of the range that the passed node holds its sum |
j | the right index of the range that the passed node holds its sum |
curr | pointer to the node to be propagated |
- Returns
- void
84 {
85 if (!curr->prop) {
86 return;
87 }
88 curr->val += (j - i + 1) * curr->prop;
89 if (i != j) {
90 curr->left =
newKid(curr->left);
91 curr->right =
newKid(curr->right);
92 curr->left->prop += curr->prop;
93 curr->right->prop += curr->prop;
94 }
95 curr->prop = 0;
96 }
std::shared_ptr< Node > newKid(std::shared_ptr< Node > const &curr)
Creating a new node with the same values of curr node.
Definition persistent_seg_tree_lazy_prop.cpp:65
◆ newKid()
Creating a new node with the same values of curr node.
values of the leaf nodes that the segment tree will be constructed with
- Parameters
-
curr | node that would be copied |
- Returns
- the new node
65 {
67 newNode->left = curr->left;
68 newNode->right = curr->right;
69 newNode->prop = curr->prop;
70 newNode->val = curr->val;
71 return newNode;
72 }
◆ query() [1/2]
int64_t range_queries::perSegTree::query |
( |
const uint32_t & | i, |
|
|
const uint32_t & | j, |
|
|
const uint32_t & | l, |
|
|
const uint32_t & | r, |
|
|
std::shared_ptr< Node > const & | curr ) |
|
inlineprivate |
Querying the range from index l to index r, checking at every node if it has some value to be propagated. Current node's value is returned if its range is completely inside the wanted range, else 0 is returned.
- Parameters
-
i | the left index of the range that the passed node holds its sum |
j | the right index of the range that the passed node holds its sum |
l | the left index of the range whose sum should be returned as a result |
r | the right index of the range whose sum should be returned as a result |
curr | pointer to the current node, which has value = the sum of elements whose index x satisfies i<=x<=j |
- Returns
- sum of elements whose index x satisfies l<=x<=r
172 {
174 if (j < l || r < i) {
175 return 0;
176 }
177 if (i >= l && j <= r) {
178 return curr->val;
179 }
180 uint32_t mid = i + (j - i) / 2;
181 return query(i, mid, l, r, curr->left) +
182 query(mid + 1, j, l, r, curr->right);
183 }
void lazy(const uint32_t &i, const uint32_t &j, std::shared_ptr< Node > const &curr)
If there is some value to be propagated to the passed node, value is added to the node and the childr...
Definition persistent_seg_tree_lazy_prop.cpp:83
int64_t query(const uint32_t &i, const uint32_t &j, const uint32_t &l, const uint32_t &r, std::shared_ptr< Node > const &curr)
Querying the range from index l to index r, checking at every node if it has some value to be propaga...
Definition persistent_seg_tree_lazy_prop.cpp:171
◆ query() [2/2]
int64_t range_queries::perSegTree::query |
( |
const uint32_t & | l, |
|
|
const uint32_t & | r, |
|
|
const uint32_t & | version ) |
|
inline |
Querying the range from index l to index r, getting the sum of the elements whose index x satisfies l<=x<=r.
- Parameters
-
l | the left index of the range whose sum should be returned as a result |
r | the right index of the range whose sum should be returned as a result |
version | the version to query on. If equals to 0, the original segment tree will be queried |
- Returns
- sum of elements whose index x satisfies l<=x<=r
246 {
247 return query(0, n - 1, l, r,
ptrs[version]);
248 }
◆ size()
uint32_t range_queries::perSegTree::size |
( |
| ) |
|
|
inline |
Getting the number of versions after updates so far which is equal to the size of the pointers vector.
- Returns
- the number of versions
◆ update() [1/2]
std::shared_ptr< Node > range_queries::perSegTree::update |
( |
const uint32_t & | i, |
|
|
const uint32_t & | j, |
|
|
const uint32_t & | l, |
|
|
const uint32_t & | r, |
|
|
const int64_t & | value, |
|
|
std::shared_ptr< Node > const & | curr ) |
|
inlineprivate |
Doing range update, checking at every node if it has some value to be propagated. All nodes affected by the update are copied and propagation value is added to the leaf of them.
- Parameters
-
i | the left index of the range that the passed node holds its sum |
j | the right index of the range that the passed node holds its sum |
l | the left index of the range to be updated |
r | the right index of the range to be updated |
value | the value to be added to every element whose index x satisfies l<=x<=r |
curr | pointer to the current node, which has value = the sum of elements whose index x satisfies i<=x<=j |
- Returns
- pointer to the current newly created node
138 {
140 if (i >= l && j <= r) {
142 newNode->prop += value;
144 return newNode;
145 }
146 if (i > r || j < l) {
147 return curr;
148 }
150 uint32_t mid = i + (j - i) / 2;
151 newNode->left =
update(i, mid, l, r, value, curr->left);
152 newNode->right =
update(mid + 1, j, l, r, value, curr->right);
153 newNode->val = newNode->left->val + newNode->right->val;
154 return newNode;
155 }
std::shared_ptr< Node > update(const uint32_t &i, const uint32_t &j, const uint32_t &l, const uint32_t &r, const int64_t &value, std::shared_ptr< Node > const &curr)
Doing range update, checking at every node if it has some value to be propagated. All nodes affected ...
Definition persistent_seg_tree_lazy_prop.cpp:135
◆ update() [2/2]
void range_queries::perSegTree::update |
( |
const uint32_t & | l, |
|
|
const uint32_t & | r, |
|
|
const int64_t & | value ) |
|
inline |
Doing range update by passing the left and right indexes of the range as well as the value to be added.
- Parameters
-
l | the left index of the range to be updated |
r | the right index of the range to be updated |
value | the value to be added to every element whose index x satisfies l<=x<=r |
- Returns
- void
223 {
225 0, n - 1, l, r, value,
227 1]));
228 }
◆ ptrs
number of elements/leaf nodes in the segment tree
◆ vec
ptrs[i] holds a root pointer to the segment tree after the ith update. ptrs[0] holds a root pointer to the segment tree before any updates
The documentation for this class was generated from the following file: