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.


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… :frowning:

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).


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… :slight_smile:


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


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

int main(){

   int n;
   printf("enter the value of n\n");

  // p[2*n-1];
  printf("enter the original array");





// free§; free(a);

return 0;

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


    return a[l];

    {    mid=(l+r)/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… :slight_smile:

Declare mid as local to sum not as global variable.

okay… now i got it… :slight_smile: