Segment Trees and range minimum query

SEGMENTED TREES

We generally come across question involving range queries and update queries which may or may not require to print output after each queries.
For example:-we have an array arr[0.....n-1] and following two queries:
1.find minimum in range [l,r] where 0<l<r<n and output it.
2.upadate each value in range [l,r] and output the new array.



Brute force approach:Run a loop for each query from l-r and find the minimum or update the array.
This approach takes O(n) time for each query and if the number of queries is large,the total time
would be of order O(m*n) {m being the number of queries} , which is not expected to be a good time
complexity.

Segmented tree approach:This approach takes O(log(n)) time to perform both the operations which is
definitely way better than O(m*n).

Representation of segment tree:
1.All the leaf nodes are the elements of the array
2.Each internal node belong to an interval and root node belonging to interval [0,n).
3.Each node will have two children ,left and right,each of whoes interval will be
[l,mid) and [mid,r) respectively, mid=(l+r)/2.

The above was a conceptual representation of a segmented tree.physically the tree is stored in the
form of an array . Each element at an index i has its children at index 2*i+1 and 2*i+2 for left
and right respectively. The tree will have atmost 4*n nodes.

In context to the minimum range query:
1. Leaf nodes represent the elements of array
2. The internal nodes will represent the minimum of all leaves below it.

How to answer range query?

You are given a range [l,r).there are three possible cases
1. Partial overlap -check both the children
2. Complete overlap - we stop here and return the value of the node
3. No overlap - in this we stop there itself and return a large value

The code is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include<bits/stdc++.h> using namespace std; void buildTree(int tree[],int arr[],int pos,int low,int high) { if(low==high) { tree[pos]=arr[low]; return; } else { int mid=(low+high)/2; buildTree(tree,arr,2*pos+1,low,mid); buildTree(tree,arr,2*pos+2,mid+1,high); tree[pos]=min(tree[2*pos+1],tree[2*pos+2]); } } int rangeQuery (int tree[],int pos, int low, int high, int l, int r) { if(l<=low&&r>=high) return tree[pos]; //total overlap if(l>high||r<low) return INT_MAX; //no overlap int mid=(low+high)/2; return min(rangeQuery(tree,2*pos+1,low,mid,l,r),rangeQuery(tree,2*pos+2,mid+1,high,l,r));//partial overlap } main() { int arr[]={1,3,5,2,6,7,8}; int tree[10]; buildTree(tree,arr,0,0,7); cout<<rangeQuery(tree,0,0,7,3,5); //min from 3-5 cout<<rangeQuery(tree,0,0,7,0,5); //min from 0-5 }

This article is contributed by Sunpriya Kaur Bhatia and i hope now you can implement segment tree without any problem. Lazy propagation will be discussed in next post.
Thanks,
Happy Coding !