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 :
-
I used 0-indexing array as opposed to 1 indexing as used in topcoder.
-
Rather than storing index in tree, I am storing the value.
Problems:
-
The tree does not store the value perfectly, I mean there are error I am unable to find.
-
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));
}