# Segment tree programming

Hi guys, I need some help implementing segment tree algorithm (Implementing RMQ in segment tree).
I read the topcoder tutorial and tried implementing myself. But I made a mistake somewhere.
Here is the changes implemented in my code :

1. I used 0-indexing array as opposed to 1 indexing as used in topcoder.

2. Rather than storing index in tree, I am storing the value.

Problems:

1. The tree does not store the value perfectly, I mean there are error I am unable to find.

2. Every search query gives the minimum value in the entire tree rather than in an interval.

Here is my code:

``````#include<stdio.h>

void create(int node,int arr[],int tree[],int i,int j,int n)

{

if(i==j)

tree[node]=arr[i];

else

{

create(node*2+1,arr,tree,i,(i+j)/2,n);

create(node*2+2,arr,tree,((i+j)/2)+1,j,n);

if(tree[node*2+1]<tree[node*2+2])

tree[node]=tree[node*2+1];

else

tree[node]=tree[node*2+2];

}

}

int search(int node,int arr[],int tree[],int i,int j,int n,int start,int end)

{

if(start<i&&end>j)

return -1;

if(start>=i&&end<=j)

return tree[node];

int p=search(node*2+1,arr,tree,i,(i+j)/2,n,start,end);
int q=search(node*2+2,arr,tree,((i+j)/2)+1,j,n,start,end);

if(p==-1)

return q;

else if(q==-1)

return p;

else

{

if(p<q)

return p;

else

return q;

}

}

int main()

{

int arr[6]={2,5,1,9,2,7};

int n=6,tree[16]={-1},temp;

create(0,arr,tree,0,5,6);

temp=n;

n=temp;

for(int i=0;i<16;i++)

{

printf("%d\t",tree[i]);

}

printf("\n%d\n",search(0,arr,tree,0,5,n,0,5));

printf("\n%d\n",search(0,arr,tree,0,5,n,0,4));

printf("\n%d\n",search(0,arr,tree,0,5,n,0,3));

printf("\n%d\n",search(0,arr,tree,0,5,n,0,2));

printf("\n%d\n",search(0,arr,tree,0,5,n,0,1));

printf("\n%d\n",search(0,arr,tree,0,5,n,0,0));

printf("\n%d\n",search(0,arr,tree,0,5,n,1,5));

printf("\n%d\n",search(0,arr,tree,0,5,n,2,5));

printf("\n%d\n",search(0,arr,tree,0,5,n,3,5));

printf("\n%d\n",search(0,arr,tree,0,5,n,4,5));

printf("\n%d\n",search(0,arr,tree,0,5,n,5,5));

printf("\n%d\n",search(0,arr,tree,0,5,n,2,3));

printf("\n%d\n",search(0,arr,tree,0,5,n,2,4));

printf("\n%d\n",search(0,arr,tree,0,5,n,1,4));

printf("\n%d\n",search(0,arr,tree,0,5,n,1,2));

printf("\n%d\n",search(0,arr,tree,0,5,n,1,3));

}``````
//