## 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

#### 104 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

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.

2. I can't understand you :)

3. 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 ?

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

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

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

6. 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 !!!

7. 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.

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

9. 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

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

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

10. This comment has been removed by the author.

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

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

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

12. 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.

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;

2. This comment has been removed by the author.

13. This comment has been removed by the author.

14. 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!!

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.

15. Can you please elaborate how to implement DQUERY?

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

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

17. 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 ?

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

19. This comment has been removed by the author.

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

21. This comment has been removed by the author.

22. 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.

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

23. 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

24. Can you do range multiplication with segment trees?

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

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

26. 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?

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

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

29. I cannot say if I understood Lazy propagation part.

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

31. i don't understand

32. thank u for your post............really helped me...........

33. 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.

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

35. This comment has been removed by the author.

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

37. 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

38. nice :)
really helpful one.

39. 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))?

40. 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

41. Writing an assignment could be tough task for you for various reasons. However, our assignment writers have ample experience in writing assignments and have much time as well.You can opt for our assignment writing service and can get a well-written assignment from us

Nda admit card 2019

42. This will help you to find detail about download festival: https://calendar.prattlibrary.org/event/community_poetree#.XMgsVegzaMq

43. 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

44. 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.

45. Shut up and kiss me. Hey, i am looking for an online sexual partner ;) Click on my boobs if you are interested (. )( .)

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

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

48. your post is awesome and very useful thanks for sharing such post

Kids Activities in Edmontons
Pray Parks Edmonton

49. i am very thankfull of you, your post is awesome and very useful thanks for sharing such post.

Paris Disney Taxi
Paris Airport Taxi Transfers
Transfer from CDG to Disney
Beauvais Airport Transfer
Orly Airport Transfer
CDG Airport Transfer

50. It's wonderfull Blog, Full of experience.

HD Eļļa
Sintētiskā Eļļa
KTM Eļļa
Honda Eļļa
Smērvielas

51. The blog post is very nice. Thank you!
Bola Tangkas Online
Gaple Online Judi

52. Blog is quite good and it's awesome to read

mega888 dl
xe88 apk download
kiss918 app download
918kiss malaysia

53. Thanks for sharing this Awesome Blog Page! Bookmarked

Interwin Blog
Online Casino Malaysia
Online Slot Malaysia

54. Thanks for sharing this Awesome Blog Page! Bookmarked

Interwin Blog
Online Casino Malaysia
Online Slot Malaysia

55. Thanks! for sharing this information with us.

Trending sports news worldwide
Gaming Reviews Malaysia

56. Hello!!!
Try our Top Online Casino Malaysia, Best Online Casino Malaysia, Online Casino Malaysia, Online Football Betting Malaysia for winning grand rewards and real jackpot with us at Vtbet88.com

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

Gaming Reviews Malaysia
Tennis News Singapore

58. Thanks!! for sharing blogger you can join us by follow -

Gaming Reviews Malaysia
Gaming Reviews Singapore

59. Thanku so much for sharing this post. This blog is relevant to my subject.
Scr888 Game
Scr888 Casino Download
Scr888 Download Link
918kiss Malaysia
Scr888
Scr888 Malaysia

60. This post is unique and interesting, thank you for sharing this awesome information and other side you can join our wonderful games like :

Sbobet Mobile Malaysia
Poker Win Game Malaysia
Malaysia Live 4d Results
Lion King Game Download

61. It’s wonderful post and very helpful, thanks for all this information.Thank you for sharing this awesome information and other side you can join our wonderful games like :

Download 918kiss
918kiss2

62. 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

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

Payment Solution
Online Payment Gateway

64. Wow very nice post i got it here.I like it.Wanna play Trusted Online Casino Singapore 2021 | Online Casino Singapore | Trusted Online Casino Malaysia

65. Your blog is great!!! Good content!! I would recommend this to my friends. Thanks

Msm60
Msm for horses
Dimethyl sulfoxide
Methyl sulfonyl methane
Msm crystals
Dimethyl sulfone

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

67. 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.