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.

Thanks in advance.

There is a detailed article : http://se7so.blogspot.com/2012/12/segment-trees-and-lazy-propagation.html

Here's my solution for SPOJ PROBLEM WHICH ASKS FOR THE SAME THING

Link Of Solution

Should I post comments also in my code as it is a little hard to read other people's code ?

Thanks.Can you take a look at my code for this problem ? I got WA. link On ubunut paste

Where have you used the concept of lazy propogation ?

Sorry.This is the code with lazy that got WA: http://paste.ubuntu.com/7866707/

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.

for practicing may be this problem be good http://www.spoj.com/problems/HORRIBLE/ and sgu's 311

I solved this problem(spoj) without lazy and got accepted. My code is here: http://paste.ubuntu.com/7866365/

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

But this code with lazy got WA. Can you say what i am doing wrong? http://paste.ubuntu.com/7866707/

line 12 add[v] != 0 line 16 += and consider the case when you call push(x) and 2 * x + 1 > MAXN => runtime error

You are right.Horrible mistake! I wrote = + instead += !!! got AC!Thanks!

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?