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

Can anyone please explain me with a proper visualization of how is this function working…

Please…

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

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

Declare mid as local to sum not as global variable.

okay… now i got it… :slight_smile: