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

Collaboration diagram for range_queries::perSegTree:

Classes
class	Node

Public Member Functions
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.

Private Member Functions
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.

Private Attributes
uint32_t	n = 0

std::vector< std::shared_ptr< Node > >	ptrs {}
	number of elements/leaf nodes in the segment tree

std::vector< int64_t >	vec {}

Detailed Description

Range query here is range sum, but the code can be modified to make different queries like range max or min.

Definition at line 39 of file persistent_seg_tree_lazy_prop.cpp.

Member Function Documentation

◆ 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

Definition at line 197 of file persistent_seg_tree_lazy_prop.cpp.

    {
        if (vec.empty()) {
            return;
        }
        n = vec.size();
        this->vec = vec;
        auto root = construct(0, n - 1);
        ptrs.push_back(root);
    }

◆ 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

Definition at line 106 of file persistent_seg_tree_lazy_prop.cpp.

                                                                        {
        auto newNode = std::make_shared<Node>(Node());
        if (i == j) {
            newNode->val = vec[i];
        } else {
            uint32_t mid = i + (j - i) / 2;
            auto leftt = construct(i, mid);
            auto right = construct(mid + 1, j);
            newNode->val = leftt->val + right->val;
            newNode->left = leftt;
            newNode->right = right;
        }
        return newNode;
    }

◆ 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

Definition at line 83 of file persistent_seg_tree_lazy_prop.cpp.

                                               {
        if (!curr->prop) {
            return;
        }
        curr->val += (j - i + 1) * curr->prop;
        if (i != j) {
            curr->left = newKid(curr->left);
            curr->right = newKid(curr->right);
            curr->left->prop += curr->prop;
            curr->right->prop += curr->prop;
        }
        curr->prop = 0;
    }

◆ newKid()

std::shared_ptr< Node > range_queries::perSegTree::newKid ( std::shared_ptr< Node > const & curr )

inlineprivate

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

Definition at line 65 of file persistent_seg_tree_lazy_prop.cpp.

                                                                {
        auto newNode = std::make_shared<Node>(Node());
        newNode->left = curr->left;
        newNode->right = curr->right;
        newNode->prop = curr->prop;
        newNode->val = curr->val;
        return newNode;
    }

◆ 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

Definition at line 171 of file persistent_seg_tree_lazy_prop.cpp.

                                                                      {
        lazy(i, j, curr);
        if (j < l || r < i) {
            return 0;
        }
        if (i >= l && j <= r) {
            return curr->val;
        }
        uint32_t mid = i + (j - i) / 2;
        return query(i, mid, l, r, curr->left) +
               query(mid + 1, j, l, r, curr->right);
    }

◆ 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

Definition at line 241 of file persistent_seg_tree_lazy_prop.cpp.

    {
        return query(0, n - 1, l, r, ptrs[version]);
    }

◆ 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

Definition at line 255 of file persistent_seg_tree_lazy_prop.cpp.

    {
        return ptrs.size();
    }

◆ 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

Definition at line 135 of file persistent_seg_tree_lazy_prop.cpp.

                                                                  {
        lazy(i, j, curr);
        if (i >= l && j <= r) {
            std::shared_ptr<Node> newNode = newKid(curr);
            newNode->prop += value;
            lazy(i, j, newNode);
            return newNode;
        }
        if (i > r || j < l) {
            return curr;
        }
        auto newNode = std::make_shared<Node>(Node());
        uint32_t mid = i + (j - i) / 2;
        newNode->left = update(i, mid, l, r, value, curr->left);
        newNode->right = update(mid + 1, j, l, r, value, curr->right);
        newNode->val = newNode->left->val + newNode->right->val;
        return newNode;
    }

◆ 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

Definition at line 219 of file persistent_seg_tree_lazy_prop.cpp.

    {
        ptrs.push_back(update(
            0, n - 1, l, r, value,
            ptrs[ptrs.size() -
                 1]));  // saving the root pointer to the new segment tree
    }

Member Data Documentation

◆ n

uint32_t range_queries::perSegTree::n = 0

private

Definition at line 52 of file persistent_seg_tree_lazy_prop.cpp.

◆ ptrs

std::vector<std::shared_ptr<Node> > range_queries::perSegTree::ptrs {}

private

number of elements/leaf nodes in the segment tree

Definition at line 54 of file persistent_seg_tree_lazy_prop.cpp.

54{};

◆ vec

std::vector<int64_t> range_queries::perSegTree::vec {}

private

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

Definition at line 57 of file persistent_seg_tree_lazy_prop.cpp.

57{};

The documentation for this class was generated from the following file:

range_queries/persistent_seg_tree_lazy_prop.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ construct() [1/2]

◆ construct() [2/2]

◆ lazy()

◆ newKid()

◆ query() [1/2]

◆ query() [2/2]

◆ size()

◆ update() [1/2]

◆ update() [2/2]

Member Data Documentation

◆ n

◆ ptrs

◆ vec