You are not logged in. Please login at www.codechef.com to post your questions!

×

topcoder Segment tree tutorial doubt

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;

}

asked 02 Nov '14, 14:24

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

edited 02 Nov '14, 17:38


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].

link

answered 02 Nov '14, 19:45

nishant2002's gravatar image

4★nishant2002
82247
accept rate: 25%

edited 02 Nov '14, 20:05

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

link

answered 06 Nov '14, 17:30

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,188
×712
×152

question asked: 02 Nov '14, 14:24

question was seen: 2,109 times

last updated: 06 Nov '14, 19:28