# Construction of a segment tree

I was reading this ARTICLE about SEGMENT TREES on geeksforgeeks and found an implementation but i am unable to clearly visualize how is this function working.

Article is based on Problem

```We have an array arr[0 . . . n-1]. We should be able to
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 arr[i] = x where 0 <= i <= n-1.
```

Function:

``````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];
}
``````

I am bad at understanding recursion… Can anyone please explain me with a proper visualization of how is this function working…

You can see this here. I would suggest understanding recursion first from basic to advance from geeks, and then start segment tree.

1 Like

I’ll like to explain the recursion part of it:

Let the given array is : `5,6,7,8` Construct the below tree, (think bottom-up manner), go to the leaves first for understanding:

``````      (5+6+7+8)         // (..) here dots denotes sum of numbers in parenthesis.
/          \
/            \
(5+6)         (7+8)
/    \        /      \
5     6       7       8
``````

For every si(index variable for the segment tree array), the node’s value is the sum of its two childs(all internal nodes).

Thus:

``````st[si] =  constructSTUtil(arr, ss, mid, st, si*2+1) // left child
+ constructSTUtil(arr, mid+1, se, st, si*2+2);  // right child
``````

If `ss==se`, we have reached the leaf nodes and thus, the value here is just the actual number and we recursively move up. Drawing recursion tree by indices may make it more clear:

``````                       st= st+st  // (ss,se)= (0,3)
/     \
(ss,se)= (0,1)-> st     st -> (ss,se) = (2,3)
/  \       /   \
(ss,se)= (0,0)-> st  st st  st-> (ss,se)= (3,3)= a
thus, st=a        /|\     |_(ss,se)= (2,2)= a
|
(ss,se)= (1,1)= a
``````

Hope it clears… Anything wrong or missing or something you don’t get, just let me know… 2 Likes

I have made on similar program for segmented tree… but it is giving wrong answer…!! plzz check it…

#include<stdio.h>
#include<stdlib.h>

int *p;
int *a;
int i;
int mid;

int main(){

``````   int n;
printf("enter the value of n\n");
scanf("%d",&n);

p=calloc(2*n-1,sizeof(int));
// p[2*n-1];
a=calloc(n,sizeof(int));
//a[n];
printf("enter the original array");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

}

sum(0,n-1,0);

for(i=0;i<(2*n-1);i++)
{
printf("%d\n",p[i]);

}
``````

// free§; free(a);

return 0;
}

int sum(int l,int r,int index)
{

``````  if(l==r)
{
p[index]=a[l];

return a[l];
}

else
{    mid=(l+r)/2;
p[index]=sum(l,mid,(2*index)+1)+sum(mid+1,r,(2*index)+2);

return p[index];
}
``````

}

Try outputting the values of l and r in the sum function and debug. I’ll see to it asap in the evening if still not answered by someone… Declare mid as local to sum not as global variable.

okay… now i got it… 