I have searched on internet about implementation of Segment trees but found nothing when it came to lazy propagation. There were some previous questions on stack overflow but they were focused on solving some particular problems of SPOJ. Though I think this is the best explanation of segment trees with pseudocode but I need to implement it with lazy propagation. I found following links :
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees
In addition to the above link, some blogs were also there but they all were giving reference to the same thread.
Example
An example of the application of this data structure would be something like, say I have been given a range of numbers from 1 to n. Now I perform some operations like adding some constant number to a particular range or subtracting some constant number from a particular range. After performing operations I'm supposed to tell the minimum and maximum number in the given number.
An obvious solution would be to perform addition or subtraction to each number in the given range one by one. But this can't be feasible in a situation in which no of operations performed are large.
A better approach would be using Segment Trees with lazy propagation technique. It says instead of performing the update operation on each number individually, just keep track of all the operations until all operations are done. Then finally perform update operation to get the minimum and maximum number in the range.
Example with real data
Suppose I have given the range [1,10] which means numbers are 1,2,3,4,5,6,7,8,9,10. Now suppose I perform an operation which decreases the numbers in the range [3,6] by 4 ,so now numbers will look like 1,2,-1,0,1,2,7,8,9,10. Now I perform another operation which increases the numbers in the range [5,9] by 1, so the number will now look like 1,2,-1,0,2,3,8,9,10,10.
Now if I ask you to tell me the maximum and minimum number then the answer will be :
Maximum = 10
Minimum = -1
This is just a simple example.The actual problem might contain thousands of such addition/subtraction operations.I hope it's clear now.
This is what I have understood so far but I guess there is no unified link on Internet which explains the concept and implementation in a better way.
Can anyone give some good explanation including pseudocode for lazy propagation in segment trees?
Thanks.