
I was wondering how to use the segment tree implementation. I adjusted it so that M[] and A[] are global arrays but I must not be using it write. The initialize() function seems to work right but the query() function doesn't. I fill A[] from 0..n1. I call initialize(1,0,n1), and for each query I call query(1,0,e1,i,j). What's the problem?
Here's my edit to the code:
void initialize(intnode, int b, int e)
{
if (b == e)
M[node] = b;
else
{
initialize(2 * node, b, (b + e) / 2, M, A, N);
initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N);
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 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);
//These assignment statements seem to be causing the trouble
//if I eliminate then and simply return p1 or p2 I have no problem
//but I suspect that the complexity is ruined because of this.
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;
}
