I was solving Range Minimum Query problem on hackerearth, here is my solution. I am getting wrong answer for tihs, anyone please explain what is problem in my code.
Can you explain your update function? The usual procedure I know is, we goto the required leaf for point update, change it, and merge the new leaf with required nodes to get parents till we reach root.
Refer to blog on codeforces http://codeforces.com/blog/entry/18051 and its diagram.
While calling query function range considered by blog is [l,r) (i.e r is exclusive) and so
[ if ((r & 1) == 1) ans = min(ans, t[–r]) ] (You can refer to diagram where range is [19,27) .
Your AC code: https://ideone.com/C6yPjE
1 Like
private static void update(int x, int y, int n) {
x += n;//to go to appropriate leaf node in the tree
t[x] = y;//update the leaf node
//below for loop updates the chain from leaf to root
for (x >>= 1; x > 0; x >>= 1) {
t[x] = min(t[x << 1], t[(x << 1) + 1]);
}
}
wrote in comments how my update function works.
I didn’t understand the query function in that blog, I didn’t understand so I coded my own. And please explain what is wrong with my query function.
If x=11 then first I will do 11+n to go to the leaf node, then I will do x>>=1 which will make x=5 then I choose min(t[x<<1],t[(x<<1)+1]) and since in this clearly x<<1=10 and (x<<1)+1 would be 11, so where is the problem. can you please explain when my code will do min(t[11],t[12]) I am not able to figure that out.
Sorry for that update () mistake .
In your query() function you consider range [l,r]
hence in for loop condition of query() function will be (l<=r) instead of (l<r) .(Eg. In case range is [6,6] then your code will not enter loop).