tag:blogger.com,1999:blog-6622840520755071788.post4828377376825326878..comments2024-02-26T02:59:08.201-08:00Comments on On Algorithm Problems: Rip Van Winkle's Codelbvhttp://www.blogger.com/profile/02965219019669114297noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6622840520755071788.post-35221011142332586582016-09-02T23:41:33.422-07:002016-09-02T23:41:33.422-07:00Have you implemented this solution? after B 120 12...Have you implemented this solution? after B 120 127: you have delta=4 at node 2. Then for C 125 127 3: you have propagated this value, how did you know which child will get 6 and which one 4?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6622840520755071788.post-82212864750974798142015-08-21T11:42:52.852-07:002015-08-21T11:42:52.852-07:00Thanks , Good job.Thanks , Good job.Anonymoushttps://www.blogger.com/profile/15889714479775992924noreply@blogger.comtag:blogger.com,1999:blog-6622840520755071788.post-60304595544477284752014-04-25T22:20:51.945-07:002014-04-25T22:20:51.945-07:00Yes it was a lot helpful.Thank you so much :)Yes it was a lot helpful.Thank you so much :)Anonymoushttps://www.blogger.com/profile/06474192551524121284noreply@blogger.comtag:blogger.com,1999:blog-6622840520755071788.post-50057498126399519152014-04-25T11:41:11.882-07:002014-04-25T11:41:11.882-07:00Hi,
If I understand you correctly, your question ...Hi,<br /><br />If I understand you correctly, your question is, where does the δ value actually come from in the code, is that right?<br /><br />In this post I briefly mention that "given that every node is implicitly associated with a given range of the array, it is easy to determine the values of k and δ in each node", which assumes certain things about how the segment tree is implemented.<br /><br />Typically, when you call a query/update operation on a Segment Tree structure, you use a set of indices to keep track of the range you're operating on (over the underlying array, not the tree itself), the current tree node, and the range of the current tree node. Those are the values that help you figure out δ (and k) inside your segtree code.<br /><br />For example, let's consider that first A operation. Let's call (i, j) the range of the operation (over the underlying array), x the index of the current tree node, and (a, b) the range of the tree node. In this case, when the segtree code is called for node 6, then these values look like this:<br /><br />i: 123<br />j: 126<br />x: 6<br />a: 124<br />b: 125<br /><br />Then, k and δ can be deduced like this:<br /><br />k = b - a + 1 = 2<br />δ = a - i = 1<br /><br />I hope this is clear. If I misunderstood you, or something is still confusing, let me know.lbvhttps://www.blogger.com/profile/02965219019669114297noreply@blogger.comtag:blogger.com,1999:blog-6622840520755071788.post-6801245321933150652014-04-21T10:10:38.359-07:002014-04-21T10:10:38.359-07:00Very nice explanation :)
I have a doubt that I wan...Very nice explanation :)<br />I have a doubt that I want to ask.In here it is required to calculate the values of "k" and "delta".I thought of doing this by following method:<br />For 'k' I would be keeping a variable in the structure called 'leaves' which serves the purpose of 'k' but what to do for 'delta'......I got thinking that to calculate 'delta' one needs the original values that are to be added to the required node.For instance in the given example when first A operation lands on the 6th node it adds 5 to sum and makes 'delta'=1 which is calculated via the method that k=2 and 2-1=3-2=1 so henceforth delta=1.But how to actually do it?<br />I am unable to understand that since we are not keeping the individual values that we are adding to a given node,how can we calculate 'delta' for the node and it's children...?<br />I would be grateful to you if you clear this doubt of mine.ThanksAnonymoushttps://www.blogger.com/profile/06474192551524121284noreply@blogger.com