Segment Trees for range queries


(Akhil Nigam) #1

We have an array arr[0 . . . n-1]. We have given q queries of type (‘1’ & ‘2’).
1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1
2 Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1. (Update operation)

One can do it this in O(n) time complexity through prefix sum algorithm but can it be more further optimised ?

Yes, through Segment tree.

Whenever we have given range queries most of the time segment tree comes into picture. We can perform both the operations in O(log n) time once given the array with segment tree.

Representation of Segment tree:

  1. Leaf Nodes are the elements of the input array.
  2. Each internal node represents some merging of the leaf nodes. The merging may be different for different problems. For this problem, merging is sum of leaves under a node.

An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2i+1, right child at 2i+2 and parent at (i-1)/2.

Building the segment tree:

Allocating memory :
int *constructST(int arr[], int n)
{
//Height of segment tree
int x = (int)(ceil(log2(n)));

//Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1; 

// Allocate memory
int *st = new int[max_size];

// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);

// Return the constructed segment tree
return st;

}

Construction of segment tree:

int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}

// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] =  constructSTUtil(arr, ss, mid, st, si*2+1) +
          constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];

}

Query for Sum of given range:

int getSum(node, l, r)
{
if range of node is within l and r
return value in node
else if range of node is completely outside l and r
return 0
else
return getSum(node’s left child, l, r) +
getSum(node’s right child, l, r)
}