persistent_seg_tree_lazy_prop.cpp File Reference

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

#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 318 of file persistent_seg_tree_lazy_prop.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

static void test ( )

static

Test implementations.

Returns

void

Definition at line 268 of file persistent_seg_tree_lazy_prop.cpp.

                   {
    std::vector<int64_t> arr = {-5, 2, 3, 11, -2, 7, 0, 1};
    range_queries::perSegTree tree;
    std::cout << "Elements before any updates are {";
    for (uint32_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i];
        if (i != arr.size() - 1) {
            std::cout << ",";
        }
    }
    std::cout << "}\n";
    tree.construct(
        arr);  // constructing the original segment tree (version = 0)
    std::cout << "Querying range sum on version 0 from index 2 to 4 = 3+11-2 = "
              << tree.query(2, 4, 0) << '\n';
    std::cout
        << "Subtract 7 from all elements from index 1 to index 5 inclusive\n";
    tree.update(1, 5, -7);  // subtracting 7 from index 1 to index 5
    std::cout << "Elements of the segment tree whose version = 1 (after 1 "
                 "update) are {";
    for (uint32_t i = 0; i < arr.size(); ++i) {
        std::cout << tree.query(i, i, 1);
        if (i != arr.size() - 1) {
            std::cout << ",";
        }
    }
    std::cout << "}\n";
    std::cout << "Add 10 to all elements from index 0 to index 7 inclusive\n";
    tree.update(0, 7, 10);  // adding 10 to all elements
    std::cout << "Elements of the segment tree whose version = 2 (after 2 "
                 "updates) are {";
    for (uint32_t i = 0; i < arr.size(); ++i) {
        std::cout << tree.query(i, i, 2);
        if (i != arr.size() - 1) {
            std::cout << ",";
        }
    }
    std::cout << "}\n";
    std::cout << "Number of segment trees (versions) now = " << tree.size()
              << '\n';
    std::cout << "Querying range sum on version 0 from index 3 to 5 = 11-2+7 = "
              << tree.query(3, 5, 0) << '\n';
    std::cout << "Querying range sum on version 1 from index 3 to 5 = 4-9+0 = "
              << tree.query(3, 5, 1) << '\n';
}