# Segment Tree Algorithm Clarification

Hey Guys,
You should all be familiar with the segment tree algorithm tutorial from TopCoder.
I have a small doubt in the same.
The code snippet for the “Query” part of the segment tree algorithm is as follows,

``````int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int j)
{
int p1, p2;

if (i > e || j < b)
return -1;

if (b >= i && e <= j)
return M[node];

p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);

if (p1 == -1)
return M[node] = p2;
if (p2 == -1)
return M[node] = p1;
if (A[p1] <= A[p2])
return M[node] = p1;
return M[node] = p2;

}
``````

Now What I’d like to know is, why are the results returned this way ‘M[node] = position’
Will that not alter the pre-initialized minimum positions ?

The assignment is wrong. Here is the code to check it out.

``````    #include<iostream>
using namespace std;

#define MAXIND 100
#define MAXN 5
int M[MAXIND];
int A[MAXN] = {5,1,2,9,0};
void initialize(int node, int b, int e, int M[MAXIND], int A[MAXN], int N)
{
if (b == e)
M[node] = b;
else
{
//compute the values in the left and right subtrees
initialize(2 * node, b, (b + e) / 2, M, A, N);
initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N);
//search for the minimum value in the first and
//second half of the interval
if (A[M[2 * node]] <= A[M[2 * node + 1]])
M[node] = M[2 * node];
else
M[node] = M[2 * node + 1];
}
}

int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int j)
{
int p1, p2;

//if the current interval doesn't intersect
//the query interval return -1
if (i > e || j < b)
return -1;

//if the current interval is included in
//the query interval return M[node]
if (b >= i && e <= j)
return M[node];

//compute the minimum position in the
//left and right part of the interval
p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);

//return the position where the overall
//minimum is
if (p1 == -1)
return M[node] = p2;
if (p2 == -1)
return M[node] = p1;
if (A[p1] <= A[p2])
return M[node] = p1;
return M[node] = p2;

}

int main(){
initialize(1, 0, 4, M, A, 5);
cout<<query(1, 0, 4, M, A, 0, 4)<<endl;
cout<<query(1, 0, 4, M, A, 0, 2)<<endl;
cout<<query(1, 0, 4, M, A, 0, 4)<<endl;
}
``````

Remove the assignment and it will work fine.