×

# topcoder Segment tree tutorial doubt

 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;  } asked 02 Nov '14, 14:24 2★bajaj6 39●1●3●5 accept rate: 0%

 0 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]. answered 02 Nov '14, 19:45 82●2●4●7 accept rate: 25%
 0 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 answered 06 Nov '14, 17:30 2★bajaj6 39●1●3●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,496
×851
×172

question asked: 02 Nov '14, 14:24

question was seen: 2,365 times

last updated: 06 Nov '14, 19:28