Problems discussed :
1) Range minmum
2) GCD
3) Most frequent
4) Max sum subarray
5) Square root
6) Toggle range
7) Inversion sequence
8) Median
9) Number of distinct element
10) Kth number
1) Range minmum
2) GCD
3) Most frequent
4) Max sum subarray
5) Square root
6) Toggle range
7) Inversion sequence
8) Median
9) Number of distinct element
10) Kth number
Lazy propagation example seems to be wrong. Actual tree updation should be in the multiples of actual value. Lazy tree updates the actual value. Lets say range, 2 -> 5, 100, tree[node]+= (5-2+1)*100; incur[node]+= 100; When you push, it should update the actual tree with updated value from incur.
ReplyDeleteShiva
That is when tree[node] stores the range sum and not the minimum. In my code it stores the minimum, so when everything in the range 2,5 is updated by 100 the minimum will increase by 100 and not by (5-2+1)*100.
DeleteYeah..I pasted RSQ.. But u haven't perform the lazy propagation. U simply added the value to incur[] variable and it is consumed nowhere..
DeleteHere's the RMQ.. Please check it out. http://ideone.com/I9iomi
Delete"U simply added the value to incur[] variable and it is consumed nowhere.."
DeleteYou're right, there was a bug in the push function, tree[node2] += tree[node] should be tree[node2] += incr[node]. Sorry about that, it's updated now.
"Here's the RMQ.. Please check it out. http://ideone.com/I9iomi"
Your code looks wrong to me.
"st[idx] += (j - i + 1) * lzy[idx];" is for sum query. For RMQ you just need to add lzy[idx] to st[idx].
Check my code.. http://ideone.com/QypmTH
ReplyDeleteShiva