Monday, December 24, 2012

Segment Trees and lazy propagation

In this topic i will explain a very interesting data structure that can be used to solve a specific set of problems. I will start by explaining its definition and the proceeding with an example problem to solve with it.

Table of contents:
  • What  is segment trees?
  • Order of growth of segment trees operations
  • Show me your code
  • Lazy propagation
  • Sample problems to try 
  • References
What is segment trees?

Segment Trees is a Tree data structure for storing intervals, or segments, It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. It only uses O(N lg(N)) storage.

A segment trees has only three operations: build_tree, update_tree, query_tree.

Building tree: To init the tree segments or intervals values
Update tree: To update value of an interval or segment
Query tree: To retrieve the value of an interval or segment

Example Segment Tree:
  • The first node will hold the information for the interval [i, j]
  • If i<j the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2+1, j]
Notice that the height of a segment tree for an interval with N elements is [logN] + 1. Here is how a segment tree for the interval [0, 9] would look like:

 

Order of growth of segment trees operations
  • build_tree: O(N lg(N)) 
  • update_tree: O(lg(N + k)) 
  • query_tree: O(lg(N + k))
K = Number of retrieved intervals or segments

Show me your code

 


Lazy Propagation 

Sometimes a segment tree operation wouldn't survive if the problem constraints is too large, here it come lazy propagation along with the segment tree.

In the current version when we update a range, we branch its childs even if the segment is covered within range. In the lazy version we only mark its child that it needs to be updated and update it when needed.




Note: Read my solution for problem Can you answer these queries I in this article.


Sample Problems to try
References

105 comments:

  1. In lazy's version, i thinks it's better if you replace update tree[2*node] and tree[2*node+1] in 49th, 50th, 80th and 81th line by lazy[2*node] and lazy[2*node+1].

    Its reason is your query is not really come down to higher level, so lazy[] should be updated

    ReplyDelete
    Replies
    1. It's a programming coding and usually, web developer doing this or creating the websites and by also it's interesting fact for creative facts pay to take class online that was on the top nowadays.

      Delete
  2. So, in line 80th:
    tree[node*2] += lazy[node]; // Mark child as lazy
    tree[node*2+1] += lazy[node]; // Mark child as lazy

    => replaced by:
    lazy[node*2] += lazy[node];
    lazy[node*2+1] += lazy[node];

    It's correct ?

    ReplyDelete
  3. Yes you are totally right :).. thanks for correcting me ;)..

    ReplyDelete
  4. The same at line 49 and 50, updated check it now and tell me :)

    ReplyDelete
    Replies
    1. At lines 72 and 73, shouldn't this be replaced by a lazy[node]? sorry, I am a beginner.

      Delete
  5. update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5
    update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12
    update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100

    So, The maximum element in the whole array should be 101
    and your final array becomes
    [6 6 6 6 6 6 6 13 13 13 13 101 101 101 101 101 101 101 101]

    but your program gives output as 117 !!!

    ReplyDelete
  6. No it should be 113, however the size of the array needs to be (1+(1<<6)) as it should be 2^(1+lg N)..

    Also there was some checks needed to be added in the lazy version.. please check it and get back to me.

    ReplyDelete
  7. Yes your segment tree size should be
    int x = (int)(ceil(log2(N)))+1;
    size = (1 << x);
    This one!

    ReplyDelete
  8. Wow! Thanks for this post, it was very helpful! However, I'm trying to implement another update_tree_val function that sets the values from a range to one value. e.g. update_tree_val(3,7,4) would set the range [3,7] to the value of 4. How can I do this using lazy propagation on your tree?

    Thanks

    ReplyDelete
    Replies
    1. It would be the same but without incrementing..

      Delete
    2. This means in line 48 ,I have to modify it to tree[node] = lazy[node];
      and in line 62, tree[node] = value; ?

      Delete
  9. This comment has been removed by the author.

    ReplyDelete
  10. in line 86 it should be
    tree[node] += (b-a+1)*lazy[node];

    ReplyDelete
    Replies
    1. I think you forgot that query returns maximum from given range
      not the sum of elements of given range

      Delete
    2. This is true only when your query is range sum and not max range.

      Delete
  11. In order to do the following:
    1.) Add x to A[i], A[i+1],...,A[j]
    2.) Output the sum of A[i],A[i+1],...A[j]
    I simply replaced max() with sum() however i am not getting the correct answer.

    ReplyDelete
    Replies
    1. also replace line 48 and 86 by tree[node] += ( b - a + 1 ) * lazy[node];
      and line 62 by tree[node] += ( b - a + 1 ) * value;

      Delete
    2. This comment has been removed by the author.

      Delete
  12. in query_tree() method we could have updated the lazy value to the tree before we look for the out of range condition.... it would result in better performance...

    am i right about it....please correct me if I am wrong!!

    ReplyDelete
    Replies
    1. yes whenever u reach a node that has pending updates ..be it in the update or query function u should always update that node.this should be a good practise.

      Delete
  13. Can you please elaborate how to implement DQUERY?

    ReplyDelete
    Replies
    1. The best link is:
      http://apps.topcoder.com/forums/;jsessionid=C7BE6D64D8F4953865BCE8B7945FA2F6?module=Thread&threadID=627423&start=0&mc=13#1060242

      Delete
  14. http://discuss.codechef.com/questions/50866/segment-trees-doubt

    ReplyDelete
  15. 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
    then how to take array of this larger size for make segment tree,how to implement ?

    ReplyDelete
  16. It should be 2^(1+lg N) not 2^N

    ReplyDelete
  17. Very good and nice blog..
    I am following your code structure in my SG tree implementation :)

    ReplyDelete
  18. This comment has been removed by the author.

    ReplyDelete
  19. Hey Note: Read my solution for problem Can you answer these queries I in this article.

    The article doesn't point to the solution. It's pointing to the problem itself. Please correct it.

    ReplyDelete
    Replies
    1. The link is now correct, thanks for pointing this out

      Delete
  20. What is the complexity of updating range
    You said O(log(n+k))
    But I read somewhere O(log n + k)
    See the link
    http://en.wikipedia.org/wiki/Segment_tree
    Suppose I want to update range(0,N-1)
    It works same like "build_tree" but the complexity is different

    ReplyDelete
  21. Can you do range multiplication with segment trees?

    ReplyDelete
    Replies
    1. of course. its same as update value with k * x (x is elements in the range)

      Delete
  22. How to initialize values in a range i.e A[i]=x(some integer) using update function in lazy propagation?

    ReplyDelete
  23. If I change (2*node) with (2*node+1) and (2*node+1) with (2*node+2) and start the node position with 0 instead of 1.Will there be any changes in the result?Why have you started node of segment tree with 1?

    ReplyDelete
  24. in 46 line when will a > b condition becomes true?.

    ReplyDelete
  25. well i still cant understand the lazy part.....what does the lazy[]array stores ?.......i mean for a particular node

    ReplyDelete
  26. I cannot say if I understood Lazy propagation part.

    ReplyDelete
  27. Great Explanation Of Segment trees
    please explain more the lazy propagation part i cannt understand it.

    ReplyDelete
  28. thank u for your post............really helped me...........

    ReplyDelete
  29. If you want to learn this in a real easy way, watch tushar roy's youtube video on segment tree along with this blog post.

    ReplyDelete
  30. D-Query can be easily solved using fast io + MO's algorithm...But using BIT is safer to avoid TLE sometimes...Nice Post...!!!

    ReplyDelete
  31. This comment has been removed by the author.

    ReplyDelete
  32. what if i have to update each nodes with different values means i m not updating whole range with unique value

    ReplyDelete
  33. Hey, this is a really intuitive post with which i learnt how a segment tree is coded!
    Could you point to me some links that will explain how the worst case complexity of updating intervals is O(log(N+k))?

    ReplyDelete
  34. The article is praiseworthy. It talks about Segment Trees and lazy propagation. The article will let you understand what are segment trees? According to the article, ‘Segment Trees is a Tree data structure for storing intervals or segments. It allows querying which of the stored segments contain a given point. A segment trees have only three operations such as build tree, update tree, and query tree.’

    Thanks,
    Essay writing service

    ReplyDelete
  35. Writing an assignment has never been so easy from two top class websites like Cheap Essay Writing Service and Cheap Essay Writing Service. Please dont hesitate to appreciate the efforts of this blog

    ReplyDelete
  36. Nice articles and your information valuable and good articles thank for the sharing information. Headphone 2020 allows you to test your finger speed on the mouse to define how speedily you can click on the mouse button. The faster you click the faster you can break the records.

    ReplyDelete
  37. Environmental assignment writing services has become very popular among students seeking Environmental Health Writing Services and environmental health essay writing services.

    ReplyDelete
  38. your blog is awesome and very useful thanks for sharing. Pray Parks Edmonton

    ReplyDelete
  39. Thanks for sharing this information on the other hand you can visit our website.

    Gaming Reviews Malaysia
    Tennis News Singapore

    ReplyDelete
  40. Hello all , such a amazing informative post that you share in this article and guys if you can interested the online casino play game for the entertainment so plz you can join us:-

    Online Casino Malaysia
    grand dragon casino

    ReplyDelete
  41. What an amazing post you have. Very Informative. Also, check out my official website:-

    Payment Solution
    Online Payment Gateway

    ReplyDelete
  42. This comment has been removed by the author.

    ReplyDelete
  43. Thanks for sharing this unique blog. It is relevant to my subject.
    Sbobet Casino Malaysia
    Malaysia 4D lottery

    ReplyDelete
  44. Have you ever thought about the fact that buying custom-written essays is not always enough to get an excellent grade? Are you shocked by this information? Well, we can explain everything to you, and we can help you achieve stunning success.

    ReplyDelete
  45. This is such a wonderful useful post guys Which is share You. Thank you!
    Guys ,if you are interested then join us Live Casino Online Malaysia.

    ReplyDelete
  46. Great information. Thanks you for the details!
    Tree Service

    ReplyDelete
  47. Wonderful post which is posted you.You are the best blogger.If you interested to playing online gaming then please visit our page Online Casino Malaysia.

    ReplyDelete
  48. You have really done the great job,wonderful blog with informative stuff,i loves to follow your blog.
    For complete details please visit,
    Exterior Rendering
    Real Estate Rendering Services
    3D Interior Rendering
    3D Visualization Studio
    Architectural visualization studio
    Realistic rendering

    ReplyDelete
  49. Today in 2022, If you suspect a Snapchat account is fake, you may easily report or block that account. Check your Snap score first, Look at the photo in your profile, Check account followers.

    How to find a fake Snapchat account

    ReplyDelete
  50. Wonderful post which is posted you.You are the best and top blogger. Thanks for Sharing!

    Mississauga house cleaning service

    ReplyDelete
  51. excellent post for us after read this amazing post check this link animeflix com its free and safe website.

    ReplyDelete
  52. Thank you for sharing such great information. It is informative, can you help me in finding out more detail!


    Best Health Care Insurance | Affordable Health Insurance | Medicare Supplement Insurance Plans

    ReplyDelete
  53. some trimmers to buy at the buytrimmer.in. Visit Now:- https://buytrimmer.in/

    ReplyDelete
  54. https://www.winbox-88malaysia.com


    https://www.winboxdownload.my

    ReplyDelete