# 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[0]= st[1]+st[2]  // (ss,se)= (0,3)
/     \
(ss,se)= (0,1)-> st[1]     st[2] -> (ss,se) = (2,3)
/  \       /   \
(ss,se)= (0,0)-> st[3]  st[4] st[5]  st[6]-> (ss,se)= (3,3)= a[3]
thus, st[0]=a[0]        /|\     |_(ss,se)= (2,2)= a[2]
|
(ss,se)= (1,1)= a[1]
``````

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â€¦