Sum of range in Segment Tree using C++

In this tute, we will discuss how to query the sum of the given range in a segment tree using C++. Read till the end to get a clear idea of the Segment Tree. Let’s use the array representation for the Segment tree in this section.

 

Before all, why use Segment trees? Let’s discuss a scenario where the segment tree can be used. Consider the scenario where an array ar[0..n-1] is given and you need to perform two operations:

  1. Given indices l & r, query the sum of ar[l..r].
  2. Given an index pos and value val, update ar[pos] to ar[pos] + val.

Both operations are expected to be performed many times. Let’s see three methods to approach this problem.

Method 1:

Use the given array to perform both the operations. Since all the elements in the range [l..r] are to be traversed, the query operation would take O(n). Array elements can be accessed in O(1) time. So, updating a single node would also take O(1) time complexity.

Method 2:

Let’s now use a prefix array. This would reduce the query operation to O(1) time complexity. But, the update operation grows to O(n) time complexity. This is due to the fact that all elements in the range [pos..n-1] would be affected by changing the value at index pos.

Method 3:

The problem seems to be like a trade-off between query and update time complexities. But, if we use a Segment tree, both the operations can be done in O(Log2n) time complexity. Because of this, segment trees can be used for frequent range_queries on arrays.

Segment Tree:

The basic idea behind segment trees is that all the elements of the array are at leaves of the segment tree. Each intermediate node would have some value associated with a range in the original array. Let’s see the key points of segment trees:

  • Segment trees are Full Binary trees. So, they either have 2 children or none.
  • They contain 2n-1 nodes.
  • All the array elements are at the leaves.
  • You always start at the root of the Segment tree for any operation.

Creation:

  1. Firstly, start at the root node and set range as [0..n-1].
  2. Then, at each level with range [l..r], assign the two children with ranges [l..(l+r)/2] and [((l+r)/2)+1..r].
  3. Continue this till l=r and assign that node with the value ar[l].
  4. If the current node has index value as idx, then its children will have indices 2*idx+1 and 2*idx+2.

Sum of range in Segment Tree in C++:

For the sum queries, you’ll have to find the sum of elements in the range l & r in the array. The following algorithm is used to answer the sum query.

  1. Firstly, start at the root node.
  2. If the current node’s range is entirely within the desired range, return this value.
  3. Else, continue with the child/children containing some elements of the desired range.
  4. Continue this till all the desired range of elements are accessed.
  5. While tracing back to the root, take sum of all the returned values. The value returned by the root is the sum of the given range.

Sum of range in Segment Tree using C++

Update operation:

To update a value, the same approach is taken. But, since only one node has to be updated, that target pos is searched for and updated. The algorithm is as follows:

  1. Firstly, start at the root node which covers the entire array.
  2. If it has children, check both left and right nodes and enter into the child which contains the pos.
  3. Continue this till the target pos is reached.
  4. Because we are using a recursive approach, we would trace back the same route to the root.
  5. Finally, add the value V to all the nodes in this route.

Update operation segment tree

After update,

Update operation
To know more about updates in Segment trees, read Node and range updates in Segment Tree using C++

Implementation:

Following is the implementation of Sum Segment Tree. The program implements construction, range query, node update on Segment Tree.

// C++ program to show Segment Tree - Sum of range
#include<bits/stdc++.h>
using namespace std;

#define MAX 100010
int tree[MAX];
vector<int> ar;

/* Function to display elements of the Segment Tree
   level by level. */
void showSegTree(int n)
{
  int i, j, h = ceil(log2(n));
  for(i=0 ; i<=h ; ++i)
  {
    for(j=0 ; j<pow(2, i) ; ++j)
      cout<<tree[int(pow(2, i)-1 + j)]<<' ';
    cout<<endl;
  }
}

/* Function to construct the Segment Tree recursively.
   At each node, if it is not the leaf, two children are
   processed further. Otherwise, the leaf is assigned an
   array alement. strt and end are range in the array,
   idx is the index used in the segment tree */
int constSegTree(int strt, int end, int idx)
{
  // Saves tree[idx] = ar[strt] and then returns tree[idx]
  if(strt == end)
    return tree[idx] = ar[strt];

  int mid = (strt + end) / 2;
  return tree[idx] = constSegTree(strt, mid, 2*idx+1) +
            constSegTree(mid+1, end, 2*idx+2);
}
void constSegTree(int n)
{
  constSegTree(0, n-1, 0);
}

/* Function to get the sum of elements of array in the
   range [strt..end]. l & r are the range of current node.
   indx is the index of node in segment tree */
int getSum(int strt, int end, int l, int r, int idx)
{
  if(strt <= l && r <= end)
    return tree[idx];
  
  if(end < l || r < strt || l > r)
    return 0;
  
  int mid = (l + r) / 2;
  return getSum(strt, end, l, mid, 2*idx+1) +
      getSum(strt, end, mid+1, r, 2*idx+2);
}
int getSum(int n, int strt, int end)
{
  return getSum(strt, end, 0, n-1, 0);
}

/* Function to update a particular node of the array in
   Segment Tree. pos is the desired index in the array.
   val is the value to be added */
void updtNode(int pos, int val, int l, int r, int idx)
{
  // pos not inside the node's range
  if(pos < l || r < pos)
    return;
  
  // Update all nodes in root <-> pos path
  tree[idx] += val;

  // Leaf node reached , i.e, No children
  if(l == r)	return;		//Exit condition

  int mid = (l + r) / 2;
  updtNode(pos, val, l, mid, 2*idx+1);
  updtNode(pos, val, mid+1, r, 2*idx+2);
}
void updtNode(int n, int pos, int val)
{
  updtNode(pos, val, 0, n-1, 0);
}

int main()
{
  int n = 7;
  ar = {18, 17, 1, 19, 15, 11, 20};

  constSegTree(n);

  cout<<"n = 7, ar = {18, 17, 1, 19, 15, 11, 20}"<<endl;
  showSegTree(n);

  updtNode(n, 2, 3);

  cout<<"\nupdtNode(n, 2, 3):"<<endl;
  showSegTree(n);

  cout<<"\nSum of ar[1..4] = "<<getSum(n, 1, 4)<<endl;

    return 0;
}

Output:

n = 7, ar = {18, 17, 1, 19, 15, 11, 20}
101 
55 46 
35 20 26 20 
18 17 1 19 15 11 0 0

Sum of ar[1..4] = 52

updtNode(n, 2, 3):
104 
58 46 
35 23 26 20 
18 17 4 19 15 11 0 0

Time Complexity:

For tree creation, it is O(n) since 2n-1 nodes are to be initialized.

For range query, it is O(Log2n) due to the fact that the height of the tree is ceil(Log2n).

Similarly, for an update operation, it is O(Log2n) due to the same reason.

Bonus: Still find it difficult to understand about range queries, node updates in segment trees? Remove all comments in the code and start tracing for your inputs. If you think this is a fast solution, Lazy propagation in the Segment tree would increase the efficiency of long overlapping queries.

Also, read:

Leave a Reply

Your email address will not be published. Required fields are marked *