Test implementations.
268 {
271 std::cout <<
"Elements before any updates are {";
272 for (uint32_t i = 0; i < arr.
size(); ++i) {
274 if (i != arr.size() - 1) {
276 }
277 }
280 arr);
281 std::cout <<
"Querying range sum on version 0 from index 2 to 4 = 3+11-2 = "
282 << tree.
query(2, 4, 0) <<
'\n';
284 << "Subtract 7 from all elements from index 1 to index 5 inclusive\n";
286 std::cout <<
"Elements of the segment tree whose version = 1 (after 1 "
287 "update) are {";
288 for (uint32_t i = 0; i < arr.size(); ++i) {
290 if (i != arr.size() - 1) {
292 }
293 }
295 std::cout <<
"Add 10 to all elements from index 0 to index 7 inclusive\n";
297 std::cout <<
"Elements of the segment tree whose version = 2 (after 2 "
298 "updates) are {";
299 for (uint32_t i = 0; i < arr.size(); ++i) {
301 if (i != arr.size() - 1) {
303 }
304 }
306 std::cout <<
"Number of segment trees (versions) now = " << tree.
size()
307 << '\n';
308 std::cout <<
"Querying range sum on version 0 from index 3 to 5 = 11-2+7 = "
309 << tree.
query(3, 5, 0) <<
'\n';
310 std::cout <<
"Querying range sum on version 1 from index 3 to 5 = 4-9+0 = "
311 << tree.
query(3, 5, 1) <<
'\n';
312}
Range query here is range sum, but the code can be modified to make different queries like range max ...
Definition persistent_seg_tree_lazy_prop.cpp:39
uint32_t size()
Getting the number of versions after updates so far which is equal to the size of the pointers vector...
Definition persistent_seg_tree_lazy_prop.cpp:255
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
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
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