tag:blogger.com,1999:blog-9126683650343594008.post5796812514825697206..comments2023-06-09T00:34:14.813-07:00Comments on Eureka!!: Segment TreeAshishhttp://www.blogger.com/profile/00334758887114196596noreply@blogger.comBlogger36125tag:blogger.com,1999:blog-9126683650343594008.post-58681997303532686032016-09-12T19:49:57.647-07:002016-09-12T19:49:57.647-07:00how to do update on interval using lazy:
update f...how to do update on interval using lazy:<br /> update func:<br /> update all from l to r with their divisorsAnonymoushttps://www.blogger.com/profile/05009910413165107946noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-53839416277072067812015-02-15T02:44:32.132-08:002015-02-15T02:44:32.132-08:00great post! great post! Nidhi Makhijanihttps://www.blogger.com/profile/09998962515924952650noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-46937945044860719912014-12-18T01:23:35.766-08:002014-12-18T01:23:35.766-08:00we have to take array size of 2^n for make segment...we have to take array size of 2^n for make segment tree of n element array,then how to make segment tree of 30 or greater elements,because 2^30 = 1073741824<br />then how to take array of this larger size for make segment tree,how to implement ?Anonymoushttps://www.blogger.com/profile/15590129979180686964noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-81350629977282604222013-12-21T13:12:04.606-08:002013-12-21T13:12:04.606-08:00Here is another nice tutorial, implemented in pyth...Here is another nice tutorial, implemented in python http://sportcoder.com/segment-trees/Anonymoushttps://www.blogger.com/profile/06021328619427969715noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-117628383823730832013-12-08T09:11:29.740-08:002013-12-08T09:11:29.740-08:00Dude, you're a life saver. Been looking all ov...Dude, you're a life saver. Been looking all over on how to query the goddamn tree and it finally makes sense!.<br />Thanks a ton!Lone Rangerhttps://www.blogger.com/profile/07410279805519193866noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-31217865890394960552013-05-11T08:52:49.375-07:002013-05-11T08:52:49.375-07:00ya got that...silly on my part :D
thanx a lot!ya got that...silly on my part :D<br />thanx a lot!Mayankhttps://www.blogger.com/profile/00548360286571189135noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-64919560185792971092013-05-09T08:23:12.573-07:002013-05-09T08:23:12.573-07:00For both min and max all you need is to add one mo...For both min and max all you need is to add one more variable to each tree node to store the minimum. And add few lines to update and query function. It should be quite similar to updating the maximum.Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-37873176132597111672013-05-09T03:56:16.586-07:002013-05-09T03:56:16.586-07:00really helpful blog. Loved how simple the explanat...really helpful blog. Loved how simple the explanation was. I had a doubt though. If i need to do a query for a range and find both the min and max in that range what should be done? I made two trees with one build function: one containing the maximums and the other containing minimums. But i cant seem to figure out how to do both the jobs with one query function i am having to call two separate functions one for maximum and one for minimum.<br /><br />ThanksMayankhttps://www.blogger.com/profile/00548360286571189135noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-4371470099838386272013-02-07T20:55:47.740-08:002013-02-07T20:55:47.740-08:00Wonderful blog! Really useful :)
I had a doubt wit...Wonderful blog! Really useful :)<br />I had a doubt with a particular question involving segment trees:<br />http://www.spoj.com/problems/IOPC1207/<br />What I can't understand is why we can use 3 independent segment trees. If we update the x range say x1 to x2, won't the corresponding segment trees on y and z axis also get affected?Viki Sharmahttps://www.blogger.com/profile/03841335447825441514noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-34483216161975561342013-01-02T07:11:04.158-08:002013-01-02T07:11:04.158-08:00nice one.. pretty straight forward article with ni...nice one.. pretty straight forward article with nice explanations.<br />Segment tree is a really important data structure for programming competitions , and articles like this are really helpful!<br /><br />Thanks :)Panagiotis Kostopanagiotishttps://www.blogger.com/profile/00379257982198552853noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-36156464119359772582012-11-16T10:08:07.840-08:002012-11-16T10:08:07.840-08:00I also pointed out that we need a new member varia...I also pointed out that we need a new member variable in every node that denotes how much increments/decrements have been done to all the children of that node.<br />The query function should be very similar to the solution I have provided at the bottom of the pageAshishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-62806698400766121182012-11-16T10:01:38.430-08:002012-11-16T10:01:38.430-08:00oh right. Thank you very much karim. I am grateful...oh right. Thank you very much karim. I am grateful that you pointed out the mistake.Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-91589668449055780142012-11-16T09:08:29.194-08:002012-11-16T09:08:29.194-08:00ok here is a query
update [1-10]
update [1-5]
q...ok here is a query <br /><br />update [1-10] <br />update [1-5]<br />query [1-10]<br /><br />here update denotes increment by 1<br /><br />so the second query would be broken into two subqueries <br />update [1-5] and update [6-10]<br />and [1-10] = max([1-5], [6-10]) <br /><br />query [1-10] will return the new value without the total offt at [1-10] so i think the update should be as follows <br /><br />tree[n].cmax = max(tree[n*2].cmax,tree[n*2+1].cmax) + tree[n].offt;karimhttps://www.blogger.com/profile/16615063842771642176noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-84961705377988483562012-11-13T15:21:34.547-08:002012-11-13T15:21:34.547-08:00Hi, could you please provide query function for ra...Hi, could you please provide query function for range modification and range sum, because I don't get it.<br /><br />For example we got array with size 10 and two queries: <br />1) add to whole array 3<br />2) get sum from element 4 to 5 inclusive<br /><br />According to your code we'll call update(1, 0, 9, 0, 9, 3) and it will update first node and break; so question is how do we implement sum function here using nlog time? thanks :)Ravinhttps://www.blogger.com/profile/13711606036782112501noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-367367238689990232012-11-12T14:54:48.916-08:002012-11-12T14:54:48.916-08:00Hi Karim,
Thank you for your interest in my blog.
...Hi Karim,<br />Thank you for your interest in my blog.<br />I think my solution is correct and consider this an incompetence on my part not to be able to explain the logic properly. If you find any test case where my solution fails, please post it here for I don't want to convey any wrong solution to the public.<br /><br />As for the explanation of your question, the idea is to add the increments to only those nodes whose all children completely lie inside the range. Thus if you take a path from any one leaf node (any one array element from the range where the increment is to be done) to the root, you will find that the increment is done to only one node in the path. This helps the prevent addition of a certain increment more than once.Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-54328386563462163422012-11-12T12:01:30.873-08:002012-11-12T12:01:30.873-08:00hi ashish i really like your tutorial specially th...hi ashish i really like your tutorial specially the part with lazy propagation but i noticed that the full source code for the program is not entirely correct (not the missing parts) but in the update function <br /><br />1 - update(n*2 , b , (b+e)/2 , i , j , val);<br />2 - update(n*2+1 , (b+e)/2 + 1 , e , i , j , val);<br />3 - tree[n].cmax = max ( tree[n*2].cmax , tree[n*2+1].cmax );<br /><br />the 3rd line i think we should add the tree[n].offt to the maximum as this maximum is not propagated so it would give incorrect results if we query this exact interval againkarimhttps://www.blogger.com/profile/16615063842771642176noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-14616927312980247252012-09-24T19:11:42.563-07:002012-09-24T19:11:42.563-07:00offt is the total increments done to the subtree r...offt is the total increments done to the subtree represented by the node.<br />Thus if one needs to find how many times certain node is incremented we need to sum the offts of all its parents.<br />cmax is the updated maximum value after updates of the subtree represented by the node.<br />cmax is updated on every updates to the node.Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-55464875514060588642012-09-23T10:42:46.761-07:002012-09-23T10:42:46.761-07:00Hi could you please explain the following :-
struc...Hi could you please explain the following :-<br />struct Node {<br />int offt;<br />int cmax;<br />} tree[5000];<br /><br />what is offt and cmax holding ?<br />when i initalize the tree , then what value should be stored at offt and cmax?<br />in the query function query(1,0,999,a,b,0);// last parameter is offt , what is the use of this parameter.<br /><br />Thanks in advanceAtul anandhttps://www.blogger.com/profile/08341353254990080901noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-11821143075660596862012-09-03T22:40:34.624-07:002012-09-03T22:40:34.624-07:00call update (1, 0, 9, left, right, some-value)
Her...call update (1, 0, 9, left, right, some-value)<br />Here b and e stand for begin and end inclusive.Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-77693271344602517232012-08-11T07:42:28.406-07:002012-08-11T07:42:28.406-07:00thanks dude. nice code.thanks dude. nice code.swathttps://www.blogger.com/profile/14384479068419512104noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-18079529607951054272012-08-04T15:44:00.517-07:002012-08-04T15:44:00.517-07:00Hi Ashish Pant, the update function doesn't se...Hi Ashish Pant, the update function doesn't seem to work properly.<br />I wonder if you could explain what is `b` and `e`? Is it the full range of the data array? If I have an array data[10], then will update is called as update(1, 0, 10, left, right, some-value)? Thanks.Anonymoushttps://www.blogger.com/profile/12018547616027515054noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-35628856700227164842012-08-02T11:12:23.432-07:002012-08-02T11:12:23.432-07:00where is the full code sirwhere is the full code sirCSLhttps://www.blogger.com/profile/05731896378220384840noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-90907767629789436862012-02-12T09:33:57.896-08:002012-02-12T09:33:57.896-08:00Nice tutorial man. Really helpful :)Nice tutorial man. Really helpful :)Nitinhttps://www.blogger.com/profile/13733183940839880958noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-88624076142414364742012-01-24T05:13:59.876-08:002012-01-24T05:13:59.876-08:00And dont call me sir. Just post your question. :)And dont call me sir. Just post your question. :)Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.comtag:blogger.com,1999:blog-9126683650343594008.post-27095333425007741482012-01-24T05:13:12.081-08:002012-01-24T05:13:12.081-08:00it think there is some mistake...what is tree[n]? ...it think there is some mistake...what is tree[n]? why is it not updated? may be i need to look at the update function.Ashishhttps://www.blogger.com/profile/00334758887114196596noreply@blogger.com