Segment Tree : Range sum problem

Segment Tree?

Take an example of an array = {1 , 4 , 8 , 11, 15, 22} , and task is to find the sum of range say (2,6) , naive approach will be to run the loop from two to six giving us an O(n) time complexity,so if we have q queries it will make it O(n*q), but we can modify it to O(q) complexity if we can pre-compute the sum such that at index “i”, In the pre-computed array we have sum from 0 to index i which make new array as sum[] = {0,1, 5, 13, 24, 39, 61} so now when we are having range sum query like (3,5) we can just compute it by sum[5] – sum[2] which gives O(q) time complexity.Now a slight modification in question , if we can change any particular number in an array at index i then we have to modify whole sum array from that index ”i” to “n” ,so if we have an alternate query of changing and finding range sum it will be giving us O(n*q) time complexity.Now the Segment tree comes to rescue , by using segment tree we can reduce the complexity from O(n*q) to O(q*log(n)) which is a big difference when n is large. Now we get the answer why Segment Tree?

Segment Tree (Divide and Conquer Solution)

Problem:We have an array a{0……….n – 1} and we have to perform two types of queries:
1)Find sum of elements from index l to r where 0 <= l <= r <= n
2)Change value at specified index arr[i] = arr[n].

I’ll take about segment in three levels:
Structure
Solution for segment tree will be:
1)If the range contains a single element,the element itself will be in that node.
2)Otherwise divide the range into two smaller ranges,each will be half the size of original.
Recursive function will be written as:

Representation:
segment tree

Construction
In construction of segment tree, I’ll give the recursive approach(top down approach), start with root node which leads to a recursive call to it’s two children(see recursive function) which are storing the sum of the range which is half the size of parent node until we reach leaf node which will be storing the original element of an array. And now this recursion will revert back storing sum of it’s child in it’s parent.So,in the parent node we will be having the sum of it’s two child.See the diagram below for more clarity. We will be using an array named as sum[] which will be storing this tree where index “i” stores the sum of parent,it’s child’s sum will be stored at 2*i and 2*i + 1.It will be a full binary tree because we are dividing segment into two parts,so we will be requiring a size of around 2*2^(ceil(log(n))) – 1 to store the binary tree. It is a binary it’s height will be log(n).

segment tree implementation

Segment tree implementation

void build (int inp_arr[], int node, int tl, int tr) {
	if (tl == tr)
		sum[node] = inp_arr[tl];
	else {
		int mid = (tl + tr) / 2;
		build (inp_arr, node*2, tl, mid);
		build (inp_arr, node*2+1, mid + 1, tr);
		sum[node] = sum[node*2] + sum[node*2+1];
	}
}

Query
Now we have created the tree .Since query operation is quite complex  I’ll explain it by example: Suppose we have to query for f(0,4) ,since we can see that there is no such node which is having this range but we can notice that f(0,4) = f(0,2) + f(3,4) and there are nodes in segment tree containing those two ranges so we can conclude that we have a general expression such that f(x,y) = f(x,z) + f(z + 1,y) .

segment tress query

When querying a segment tree, we select a subset of the nodes with the property that the union of their sets is exactly the interval whose sum we seek. To do so, we start at the root and recurse over nodes whose corresponding intervals have at least one element in common with the query interval. Hence, in our example of f (0,4), we notice that both the left and right subtrees contain elements in the query interval; hence, we recurse on both. The left child of the root serves as a base case(See the figure), since its interval is contained entirely within the query interval; hence it is chosen. At the right child of the root, we notice that its left child has descendants in the query interval(figure), but its right does not; hence we recurse on the former and not the latter. The former is now another base case, and it is chosen and then we return the sum of given range.

Time Complexity:Since it is a binary tree so for query it will be taking O(log n).You can check by yourself.

int sum_query (int node,int l, int r,int tl, int tr) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return sum[node];
	int tm = (tl + tr) / 2;
	return sum_query (2*node,l, min(r,tm),tl, tm) 
               + sum_query (2*node + 1,max(l,tm + 1), r,tm + 1, tr);
}

Update
Now in update you just have to check the index of the number in which interval it exist then choosing that interval recursively till we reach the leaf of the tree and updating that leaf,now while you are recursing back you just have to update the node in which the index is such that l <= index <=r (l and r is the range of the node,index is the value to be updated).Below is the code for updating the tree.

void update (int node, int tl, int tr, int pos, int new_val) {
	if (tl == tr)
		sum[node] = new_val;
	else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update (node*2, tl, tm, pos, new_val);
		else
			update (node*2+1, tm+1, tr, pos, new_val);
		sum[node] = sum[node*2] + sum[node*2+1];
	}
}

Time Complexity:Since the height of segment tree is (log n),so for worst case time complexity for update will be O(log n).

Questions for practice:
Easy:
http://www.spoj.com/problems/GSS1/
http://www.spoj.com/problems/KGSS/
http://www.spoj.com/problems/HORRIBLE/

Medium:
http://www.codechef.com/problems/QSET
http://www.codechef.com/problems/FLIPCOIN

  • Mohit Gupta

    Very Helpful Thanks 🙂

  • Ritik Verma

    where is the code sir ?

    • http://algorithmsandme.com/ Jitendra Sangar

      Just added. Due to migrations, somethings went missing.

      • crackerplace

        The query function is not present.Its update at both places.
        query might be this from your gists.https://gist.github.com/sud-curiosum/9789f194a9cbd07a84d6

        • http://algorithmsandme.com/ Jitendra Sangar

          Updated the post.

        • http://algorithmsandme.com/ Jitendra Sangar

          Updated the post.

  • crackerplace

    Really good explanation of how query works as its little tough to get it at first shot.

  • crackerplace

    Really good explanation of how query works as its little tough to get it at first shot.