range_queries::perSegTree Class Reference

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.

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

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

Here is the call graph for this function:

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

                                                                        {
        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;
    }

Here is the call graph for this function:

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

                                               {
        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;
    }

Here is the call graph for this function:

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

                                                                {
        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

                                                                      {
        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);
    }

Here is the call graph for this function:

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

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

Here is the call graph for this function:

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

    {
        return ptrs.size();
    }

Here is the call graph for this function:

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

                                                                  {
        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;
    }

Here is the call graph for this function:

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

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

Here is the call graph for this function:

Member Data Documentation

ptrs

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

private

number of elements/leaf nodes in the segment tree

{};  /// ptrs[i] holds a root pointer to the segment tree after the

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

{};  /// values of the leaf nodes that the segment

---

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

• range_queries/persistent_seg_tree_lazy_prop.cpp