### Mr.ink's blog

By Mr.ink, 8 years ago,

I am learning segment tree with lazy propagation but i can't find good tutorial. Can anyone post a code that implements this two operation with segment tree and lazy propagation:

a-add a value to every element in a interval b-get the. sum of interval.

• +1

 » 8 years ago, # |   0 There is a detailed article : http://se7so.blogspot.com/2012/12/segment-trees-and-lazy-propagation.html Operation #1: Increment the elements within range [i, j] with value val Operation #2: Get max element within range [i, j]
 » 8 years ago, # | ← Rev. 3 →   0 Here's my solution for SPOJ PROBLEM WHICH ASKS FOR THE SAME THING Link Of SolutionShould I post comments also in my code as it is a little hard to read other people's code ?
•  » » 8 years ago, # ^ |   0 Thanks.Can you take a look at my code for this problem ? I got WA. link On ubunut paste
•  » » » 8 years ago, # ^ |   0 Where have you used the concept of lazy propogation ?
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 Sorry.This is the code with lazy that got WA: http://paste.ubuntu.com/7866707/
 » 8 years ago, # |   0 http://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%A8%D8%A7%D8%B2%D9%87%E2%80%8C%D9%87%D8%A7 in this page the second code is an implemention of a segment tree which can change a segment numbers to a number and find the maximum number of a segment.
•  » » 8 years ago, # ^ |   0 for practicing may be this problem be good http://www.spoj.com/problems/HORRIBLE/ and sgu's 311
•  » » » 8 years ago, # ^ |   0 I solved this problem(spoj) without lazy and got accepted. My code is here: http://paste.ubuntu.com/7866365/
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   0 yes your solution solves it without lazy propagation.i can remember another problem which could be solved by this trick.it was cf's "water tree".
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 But this code with lazy got WA. Can you say what i am doing wrong? http://paste.ubuntu.com/7866707/
•  » » » » » » 8 years ago, # ^ |   0 line 12 add[v] != 0 line 16 += and consider the case when you call push(x) and 2 * x + 1 > MAXN => runtime error
•  » » » » » » » 8 years ago, # ^ |   0 You are right.Horrible mistake! I wrote = + instead += !!! got AC!Thanks!
 » 6 years ago, # |   -11 Is lazy propagation always applicable for a segment tree problem ? Suppose we have to find the lcm of a given range, and there are range update operation of adding a number to the range. Is Lazy propagation applicable here?