About Segment Tree(How to build Segment Tree,C++)

Intro:-

We always see some query type questions on coding websites like hackerearth,hackerrank etc.

For eg- You have been given an array of size (N),and you have to answer some queries.

Let us see what are these queries,

In each query you have to tell the minimum element in the range [L,R],where

0 <= L, R < N (Taking 0 indexing of array) .

Let us take a sample example for understanding,

array ={ 1 , 2 , 3 , 4 , 5 }

so size of array is 5,

and queries are (in form of [L,R])

Query 1) 0 3

2) 2 4

3) 1 4

Answers:- For 1st query answer is minimum element in the range [0,3]

as we can see array[0]=1

array[1]=2

array[2]=3

array[3]=4

So, definitely the minimum is array[0]=1,

so 1 is answer for 1st query,

Similarly for other queries we can find out the minimum element.

Approaches:-

---Brute Force--

A simple solution is to iterate on array from L to R and find out the minimum element from the range.

But If we talk about worst scenario ,Let us suppose there are 10^5 queries and the constraint on size of array is 1 <= N <= 10^5,

So you can easily figure out that if each query is executed using brute force so you will definitely get TLE.

So how to avoid TLE, we will use Segment Tree for this.

---Segment Trees--

What is Segment Tree:-

As the name suggests (segments) we need to divide our range of array into some segments.That's why creation of segment tree comes under Divide And Conquer Approach.

Let us see how,

At root node we are having whole range of array,

For eg:- array ={ 1 , 2 , 3 , 4 , 5 , 6 }

As size of array is 6,so range is [ 0 - 5 ],

so at root node we are having range [ 0 - 5 ],

Now let us talk about Left and Right child of root node,

Take middle of range ,here (0+5)/2=2,

so Left child is having range [ 0 - 2 ]

and for Right child will be the remaining range from [middle + 1 to end ] i.e. here will be [3 - 5]

At each node we have to divide the range into left and right part until we will end up on a single node.

As in tree [0] , [1] , [2] , [3] , [4] , [5] are single nodes and they are called as leaf nodes of segment tree.

We know the values of all these single nodes as,

Now all leaf nodes have been filled up with the values,

So next we have to find the answers of each non-leaf nodes,

How will we do that:- For each Non-Leaf node , Just take the minimum (If we are creating the tree for finding out minimum element in range) of left and right child answers and store.

This steps will be taken care of by using recursion.

Let us see what answers will our tree store after the creation,

Analyse the tree in bottom up manner,

first we have taken minimum of [0] and [1] and stored it in the node with range [ 0- 1] ,

similarly we have taken the minimum of [3] and [4] and stored it in the node with range [ 3 - 4 ],

So you can see from the tree (Blue line symbolizes the comparison and corresponding result at each step).

Code for Building a Segment Tree:-

void bst(ll *a,ll *tree,ll s,ll e,ll idx)
{
	if(s>e)
	return;
	if(s==e)
	{
		tree[idx]=a[s];
		return;
	}
	ll mid=(s+e)/2;
	// Left
	bst(a,tree,s,mid,2*idx);
	// Right
	bst(a,tree,mid+1,e,2*idx+1);
	tree[idx]=min(tree[2*idx],tree[2*idx+1]);
}  

What all parameters we are passing,

a ---- Array of numbers.

tree ---- we are creating segment tree using array, so it is an array

s ---- starting point of range

e ---- ending point of range

idx ---- index of current node,

Now observe from the tree,

I am taking index for root node as idx (1 for root node)

then its Left Child will be having index as --- 2*idx,

and its Right Child will be having index as ---- 2*idx+1,

Actually segment tree is a full binary tree, so if you start numbering the nodes from left to right level by level,then you get this relationship between parent and its children.

If the size of array is (N),

then we will have to take the size of corresponding tree as (4*N+1)

Let us look at main function,

#define ll long long int

int main() {
	ll n;
	cin>>n;
	ll a[n];
	for(ll i=0;i<n;i++)
	cin>>a[i];
	ll *tree=new ll[4*n+1];
	ll idx=1;
	bst(a,tree,0,n-1,idx);
        return 0;
}

So here in position of (s) we are passing 0(starting point of range)

and in position of (e) we are passing (n-1)(ending point of range)

And idx as 1 (Index for root node as 1)

Let us analyze what is happening in bst function,

First of all you have to write the exit condition from recursion,

in our case it is,

if(s > e)

return;

and if any point of time (s) becomes equal to (e), that means we have reached at the leaf node,and hence value of leaf node will be same as the value of element at position (s) in array (a),that's why we stores tree[idx]=a[s]

now its time to build left and right subtree as well,

so we calculated the mid value as (s+e)/2,

and recurse for left child from [ s - mid ] with index of left child as 2*idx,

and recurse for right child from [ mid+1 - e ] with index of right child as 2*idx + 1,

At last for each node we have to store the minimum of left and right child answers,

that's why we are doing

tree[idx]=min(tree[2*idx],tree[2*idx+1]),

So that's it for the building of segment tree.

Thanks,

I hope you liked it.