tag:blogger.com,1999:blog-1178502623745690038.post4247610864466447160..comments2023-09-23T08:29:28.881-07:00Comments on Let us code: Segment TreesAnonymoushttp://www.blogger.com/profile/06820089241447673511noreply@blogger.comBlogger119125tag:blogger.com,1999:blog-1178502623745690038.post-81775485621863746232019-06-01T02:45:55.191-07:002019-06-01T02:45:55.191-07:00Thanks brother for helping me.
HELPR2D2 editorial ...Thanks brother for helping me.<br />HELPR2D2 editorial or hints- <br />The doubt may be is how to apply binary search.<br />Lets say for a sample case K=100 and u already have inserted 50, 60, 90, and now u want to insert 30. Now as clearly can be seen 30 can be inserted anywhere except the third ship which has only space left is 10 units.<br />So question is as it is not in a continuous yes or no form so how to use binary search??<br />Now lets say I have total ships of 10.<br />Now in first step of segments search for update operation in [1,10] we recursively update for [1,5] and [6,10].<br />we will maintain a max_ variable for every interval. max_ denotes maximum space in any container in that range for eg for [1,3] max_=50 as ( 1st has 50 units, 2nd has 40 units left and 3rd has 10 units left).<br />Now we want to insert in minimum index.<br />so we start from checking [1,5] and [6,10].<br />first we will check [1,5]... Now if [1,5].max_>=container then we will recurse to [1,5] and there is no need even to check for [6,10] as we r not going to put this container there. Otherwise if [1,5].max_=cont_space)<br /> update(2*idx+1,l,mid,cont_space);<br /> else<br /> update(2*idx+2,mid+1,r,cont_space);<br /> tr[idx].max_=max(tr[2*idx+1].max_,tr[2*idx+2].max_);<br /><br />now in our case [1,5].max_>=30 (as container 4 and 5 are empty and hence full space, so [1,5].max_=100 and container we want to insert is only 30 units ) <br />so we will move to [1,5].<br />now<br />[1,5] is divide into [1,3] ans [4,5] <br />now [1,3].max_>=30 ([1,3].max_==50)<br />now<br />[1,3] is divided into [1,2] and [3,3]<br />[1,2].max_>=30;<br />now,<br />[1,2] divided into [1,1] and [2,2]<br />and<br />[1,1].max_>=30 ([1,1].max_=50 and since both indexes are same so we will insert here)<br />now change [1,1].max_-=container_space;<br />Only task left how to propagate these values to ranges we visited. the last line in my code does that. <br />If u feel that u have understood it partially then just attempt it and u will easily do it.<br />if feel helped then help other by writing some editorial for some problem u solved.(on codechef as its a headache without editorials) .Anonymoushttps://www.blogger.com/profile/13173415774463075666noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-49959592268459653832018-06-11T23:30:46.114-07:002018-06-11T23:30:46.114-07:00Awesome site to get more traffic. This blogsite is...Awesome site to get more traffic. This blogsite is most site for search engine…. This site is best site in google Search…tankyu<br /><a href="http://gurumaata.com" rel="nofollow">husband Wife Problems Solve</a><br /><a href="http://Onlinevashikaranlady.biz" rel="nofollow">Vashikaran Expert</a><br /><a href="http://vashikaranlady.biz" rel="nofollow"> Online Vashikaran lady Specialist</a><br /><a href="http://blackmagicspecialistlady.biz" rel="nofollow">Love spell vashikaran</a><br /><a href="http://ushadeviastrologer.com" rel="nofollow">Vashikaran Tips</a><br />Anonymoushttps://www.blogger.com/profile/02459803894948496494noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-34618115449112457872018-06-11T23:30:00.248-07:002018-06-11T23:30:00.248-07:00Awesome site to get more traffic. This blogsite is...Awesome site to get more traffic. This blogsite is most site for search engine…. This site is best site in google Search…tankyu<br /><a href="http://gurumaata.com" rel="nofollow">husband Wife Problems Solve</a><br /><a href="http://Onlinevashikaranlady.biz" rel="nofollow">Vashikaran Expert</a><br /><a href="http://vashikaranlady.biz" rel="nofollow"> Online Vashikaran lady Specialist</a><br /><a href="http://blackmagicspecialistlady.biz" rel="nofollow">Love spell vashikaran</a><br /><a href="http://ushadeviastrologer.com" rel="nofollow">Vashikaran Tips</a><br />Anonymoushttps://www.blogger.com/profile/02459803894948496494noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-28291520759067478582018-05-23T08:21:24.435-07:002018-05-23T08:21:24.435-07:00getting wa for BRCKTS, I have used +1 for '(&#...getting wa for BRCKTS, I have used +1 for '(' and -2 for')' and done arithematic calculations accordingly<br />https://ideone.com/vymv2vHardikhttps://www.blogger.com/profile/12796901805992120186noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-82561924425758563522018-05-23T08:12:47.775-07:002018-05-23T08:12:47.775-07:00hey can anyone have a look at my code for BRCKTS, ...hey can anyone have a look at my code for BRCKTS, don't why I am getting wa<br />I have set value of '(' 1 and ')' -2 and made construct and update such that tree[0] is 0 only if correct bracket expression<br />https://ideone.com/vymv2v<br />Hardikhttps://www.blogger.com/profile/12796901805992120186noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-125311548568042392018-04-12T01:08:35.991-07:002018-04-12T01:08:35.991-07:00Thank you for Informative Post!!!
Keep it up
Bina...Thank you for Informative Post!!!<br />Keep it up <br /><a href="https://mybinaryoptionssignals.com" rel="nofollow">Binary Options Tutorial</a>William Stinnerhttps://www.blogger.com/profile/09317408991456512382noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-26388563854906127352016-12-30T05:38:33.391-08:002016-12-30T05:38:33.391-08:00This content creates a new hope and inspiration wi...This content creates a new hope and inspiration with in me. Thanks for sharing article like this. The way you have stated everything above is quite awesome. Keep blogging like this. Thanks.<a href="http://www.design3i.com/school-promotional-video-uk/" rel="nofollow">school promotional video uk</a><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-24604983143285530582016-07-25T02:20:07.937-07:002016-07-25T02:20:07.937-07:00Thanks for your share ;-)Thanks for your share ;-)烟老https://www.blogger.com/profile/03431584876983949211noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-87295788797816112022016-02-10T03:15:11.410-08:002016-02-10T03:15:11.410-08:00Thanks ! Thanks ! anurag121https://www.blogger.com/profile/07100742642640031757noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-55557614563900752252016-02-05T22:38:27.008-08:002016-02-05T22:38:27.008-08:00Here you go: http://ideone.com/WBiVSu
you mainly w...Here you go: http://ideone.com/WBiVSu<br />you mainly want to look at defn of struct `node`. Everything before that is just my standard segtree template.Anonymoushttps://www.blogger.com/profile/06820089241447673511noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-59225452564060609612016-02-05T08:55:55.018-08:002016-02-05T08:55:55.018-08:00Hi, Could you tell me how to apply lazy propagatio...Hi, Could you tell me how to apply lazy propagation for the two queries in the question SEGSQRSS (spoj)? Specifically, how to handle it to avoid overwriting of queries ?anurag121https://www.blogger.com/profile/07100742642640031757noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-56168292576007342642015-08-10T09:46:30.279-07:002015-08-10T09:46:30.279-07:00I have few doubts in the file range_min_segtree.cp...I have few doubts in the file range_min_segtree.cpp:<br />i) in line 12 & 13 : for the left branch we are going till mid nd for right branch from mid. Wont it be mid+1?<br />ii) in line 17 : ''return range_update(1,1<<n,1<<(n+1),pos+(1<<n),pos+1+(1<<n),new_val)'' , 4th argument is 1 more than 3rd. Wont it be same as 3rd as it refers to update in only one node? as for comparision <=v is used and not <v.<br />Thanks in advance, I know its too late here but It will help a lot if you take time to comment.Anonymoushttps://www.blogger.com/profile/17473918494028922097noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-20347394683909961182015-08-10T09:29:42.220-07:002015-08-10T09:29:42.220-07:00This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/17473918494028922097noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-51283704953376107462015-07-08T00:19:13.059-07:002015-07-08T00:19:13.059-07:00for the very first part,i guess your code won'...for the very first part,i guess your code won't run correctly if the numbers of element in an array is not a power of 2Anonymoushttps://www.blogger.com/profile/03950609281861413962noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-3220566879680906632015-05-17T21:01:38.728-07:002015-05-17T21:01:38.728-07:00Can you please explain me , what is n? Is it the n...Can you please explain me , what is n? Is it the number of given input? Cause for bigger number of n , tree[1<<(n+1)] will give error.Anonymoushttps://www.blogger.com/profile/10234470164210380674noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-31230011674113810992015-04-19T04:54:29.025-07:002015-04-19T04:54:29.025-07:00Hello,
could you tell me how to study your blog as...Hello,<br />could you tell me how to study your blog as it only contains code snippets and no explanation.<br />Am I missing something cause other fellow programmers seems to like it a lot but I could not understand it.<br />Anonymoushttps://www.blogger.com/profile/07710205829182200252noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-12370301055017203032015-03-04T12:29:23.696-08:002015-03-04T12:29:23.696-08:00This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/14354082644332458099noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-16032943322563822032015-03-04T12:27:16.527-08:002015-03-04T12:27:16.527-08:00All code from this page is missing. Does anyone kn...All code from this page is missing. Does anyone know where to find it?Anonymoushttps://www.blogger.com/profile/14354082644332458099noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-57661859253568305582014-12-28T01:44:13.570-08:002014-12-28T01:44:13.570-08:00I can't see the code of various part(i can onl...I can't see the code of various part(i can only see theory and link's) in your blog which i was able to see earlier.<br />Is their any problem from my side or have you removed it, using chrome browser.Anonymoushttps://www.blogger.com/profile/10882500018676315553noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-60623711749860143742014-10-08T09:18:04.163-07:002014-10-08T09:18:04.163-07:00Very Helpful :)Very Helpful :)Anonymoushttps://www.blogger.com/profile/13851751186873352999noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-59951522727319925892014-08-22T13:12:47.283-07:002014-08-22T13:12:47.283-07:00For some reason, I can't see any code on this ...For some reason, I can't see any code on this page, which used to be there before. I tried both chrome and firefox.Anonymoushttps://www.blogger.com/profile/06531259608889783774noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-78524963921921350592014-07-31T19:35:06.220-07:002014-07-31T19:35:06.220-07:00Hi I am very much new to segment tree and trying t...Hi I am very much new to segment tree and trying to understand it.<br />Your work is great.But there are some doubts in my mind which I want to clear.<br />In your example.1.b) how does the range_update work?<br />Suppose I have an array of 4 elements arr[1...4] and I want to update the 3rd element.<br />So in the tree the 3rd and 4th element will be 6th and 7th leaf.And the node 3 in the tree will hold the minimum of the segment arr[3...4] or the minimum of the two leaves 6 and 7.<br />As I have understood as per your code the range_update operation will update the value of the first parent node whose range will contain the targeted position.In this case it will update the node 3 and the root node.But it will not update the targeted leaf as the operation is not propagating down.<br />In this case without updating the leaf 6(which is the target) i am updating the parent node 3 with new_value.And I am also not considering the value of it's another child leaf 7.The value of node 7 can be less than the val of new_value.<br />So how does it work?How I can change the value of a parent node without changing the targeted leaf and without considering it's other descendents?In a minimum_query operation the minimum of all it's descendents will be stored in the parent node.<br />Pls clear my concept.Thank u. Anonymoushttps://www.blogger.com/profile/14032859000668633887noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-53704118254724422472014-07-19T06:43:41.904-07:002014-07-19T06:43:41.904-07:00I love this framework, and I have been using it al...I love this framework, and I have been using it all the time since I discovered it here.<br />One thing I've noticed is that my `split` is always identical to just doing two `update_single_subtree`'s. I notice that it is the same in your code (or at least wouldn't make a difference to the result).<br />Can you think of any problems where `split` has to be significantly different from doing two `update_single_subtree`'s?Thomas DAhttps://www.blogger.com/profile/03696428813548999653noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-13249587428461220412014-03-13T07:16:32.370-07:002014-03-13T07:16:32.370-07:00Thank you very much, that was very helpful.Thank you very much, that was very helpful.Anonymoushttps://www.blogger.com/profile/03190668728540031665noreply@blogger.comtag:blogger.com,1999:blog-1178502623745690038.post-68225025458593765002014-03-09T22:37:35.309-07:002014-03-09T22:37:35.309-07:00I havent written much on offline processing becaus...I havent written much on offline processing because they dont need something new from segment trees. Offline processing is an independent technique in itself.<br /><br />Most of the times, offline processing is used when you cant solve a problem for arbitrary subranges, but it can be solved for prefixes. For example, you cant answer query (3, 74), query(9, 12) etc efficiently, but you can answer query(0, 12), query(0, 100) etc efficiently.<br /><br />For all queries starting at same point, you build a single segment tree and answer those queries. For example, if you build one segtree for the subarray from index 3 onwards, then any query of the form qeury(3, _) can be answered using this segtree.<br /><br />However, you might have to build O(n) segment trees if you construct a new segtree for every possible start position. This can be optimized by building one segment tree at the beginning, and then the segtree for subsequent suffixes are built by updating the last segtree. For example, you first build a segment tree for array starting from index 0 onwards, and answer all queries of form (0, _). Then you update the tree in such a manner that it can answer queries of the form (1, _) correctly. Then you answer all queries of the form (1, _). Then you again update the tree so that it can answer queries of the form (2, _) correctly. So on.Anonymoushttps://www.blogger.com/profile/06820089241447673511noreply@blogger.com