TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
persistent_seg_tree_lazy_prop.cpp File Reference

Persistent segment tree with range updates (lazy propagation) More...

#include <cstdint>
#include <iostream>
#include <memory>
#include <vector>
Include dependency graph for persistent_seg_tree_lazy_prop.cpp:

Go to the source code of this file.

Classes

class  range_queries::perSegTree
 Range query here is range sum, but the code can be modified to make different queries like range max or min. More...
class  range_queries::perSegTree::Node

Namespaces

namespace  range_queries
 for std::vector

Functions

static void test ()
 Test implementations.
int main ()
 Main function.

Detailed Description

Persistent segment tree with range updates (lazy propagation)

A normal segment tree facilitates making point updates and range queries in logarithmic time. Lazy propagation preserves the logarithmic time with range updates. So, a segment tree with lazy propagation enables doing range updates and range queries in logarithmic time, but it doesn't save any information about itself before the last update. A persistent data structure always preserves the previous version of itself when it is modified. That is, a new version of the segment tree is generated after every update. It saves all previous versions of itself (before every update) to facilitate doing range queries in any version. More memory is used ,but the logarithmic time is preserved because the new version points to the same nodes, that the previous version points to, that are not affected by the update. That is, only the nodes that are affected by the update and their ancestors are copied. The rest is copied using lazy propagation in the next queries. Thus preserving the logarithmic time because the number of nodes copied after any update is logarithmic.

Author
Magdy Sedra

Definition in file persistent_seg_tree_lazy_prop.cpp.

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit

Definition at line 319 of file persistent_seg_tree_lazy_prop.cpp.

319 {
320 test(); // run self-test implementations
321 return 0;
322}
static void test()
Test implementations.

◆ test()

void test ( )
static

Test implementations.

Returns
void

Definition at line 269 of file persistent_seg_tree_lazy_prop.cpp.

269 {
270 std::vector<int64_t> arr = {-5, 2, 3, 11, -2, 7, 0, 1};
272 std::cout << "Elements before any updates are {";
273 for (uint32_t i = 0; i < arr.size(); ++i) {
274 std::cout << arr[i];
275 if (i != arr.size() - 1) {
276 std::cout << ",";
277 }
278 }
279 std::cout << "}\n";
280 tree.construct(
281 arr); // constructing the original segment tree (version = 0)
282 std::cout << "Querying range sum on version 0 from index 2 to 4 = 3+11-2 = "
283 << tree.query(2, 4, 0) << '\n';
284 std::cout
285 << "Subtract 7 from all elements from index 1 to index 5 inclusive\n";
286 tree.update(1, 5, -7); // subtracting 7 from index 1 to index 5
287 std::cout << "Elements of the segment tree whose version = 1 (after 1 "
288 "update) are {";
289 for (uint32_t i = 0; i < arr.size(); ++i) {
290 std::cout << tree.query(i, i, 1);
291 if (i != arr.size() - 1) {
292 std::cout << ",";
293 }
294 }
295 std::cout << "}\n";
296 std::cout << "Add 10 to all elements from index 0 to index 7 inclusive\n";
297 tree.update(0, 7, 10); // adding 10 to all elements
298 std::cout << "Elements of the segment tree whose version = 2 (after 2 "
299 "updates) are {";
300 for (uint32_t i = 0; i < arr.size(); ++i) {
301 std::cout << tree.query(i, i, 2);
302 if (i != arr.size() - 1) {
303 std::cout << ",";
304 }
305 }
306 std::cout << "}\n";
307 std::cout << "Number of segment trees (versions) now = " << tree.size()
308 << '\n';
309 std::cout << "Querying range sum on version 0 from index 3 to 5 = 11-2+7 = "
310 << tree.query(3, 5, 0) << '\n';
311 std::cout << "Querying range sum on version 1 from index 3 to 5 = 4-9+0 = "
312 << tree.query(3, 5, 1) << '\n';
313}
Range query here is range sum, but the code can be modified to make different queries like range max ...
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 > 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 ...
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...
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...