topcoder Segment tree tutorial doubt

general
, ,
1

topcoder segment tree tutorial why the code for query is modifying the content of M array in last 4 lines of code return M[node]=p2 .Instead of this he could have just returned the node index.

Modified M array won’t be able to handle future RMQ [range minimum Queries].

 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;

}

1 Like
2

For any range, we will use M[node], as it is, only if it is completely in range, (as repeating the procedure for that same range will give same value).

However, in case of some range, which is just a part of M[node]'s range, we are not actually looking for that whole range covered by M[node], we will recompute position of minimum element for our range and use the new value.

If a node is not in required range, -1 is returned, and it is ignored. Only those values, which are in required range are compared and minimum is computed of of them and position of this minimum is again put in the M[node] and we use this new M[node].

We don’t care if previous M[node] consisted of a different range. We have re-computed new one for our own range. And this re-computation will always happen whenever there is a difference in required range and range of a particular M[node].

3

but whey we need to recompute ??? for eg … if 1st RMQ intersects the leaves on left and right side of the root… then we are modifying the M[root]. Thus M[root] will contain the minimum of 1st RMQ query.

Now when we fire 2nd RMQ which perfectly intersects the root node i.e RMQ[0…n-1]… then we will get wrong result…or we need to recompute the minimum ??

link text