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

52 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
  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. This comment has been removed by the author.

    ReplyDelete
  13. 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
  14. 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
  15. http://discuss.codechef.com/questions/50866/segment-trees-doubt

    ReplyDelete
  16. 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
  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. Wow,,, This is great blog... Thanks for sharing this informative Content here....

    We offfers Tree Trimming in Sacramento, Contact us now for Tree Pruning in Sacramento

    Source: Best Tree Company in Sacramento www.cisnerostreecare.com

    ReplyDelete