# Lazy Propagation (concept )

I am trying to understand the concept of lazy propagation in segment trees but I am unable to
(ps. especially the part where the node is updated
by multiplying (end-start+1)*val )

void updateRange(int node, int start, int end, int l, int r, int val)
{
if(lazy[node] != 0)
{
// This node needs to be updated
tree[node] += (end - start + 1) * lazy[node];    // Update it
if(start != end)
{
lazy[node*2] += lazy[node];                  // Mark child as lazy
lazy[node*2+1] += lazy[node];                // Mark child as lazy
}
lazy[node] = 0;                                  // Reset it
}
if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
return;
if(start >= l and end <= r)
{
// Segment is fully within range
tree[node] += (end - start + 1) * val;
if(start != end)
{
// Not leaf node
lazy[node*2] += val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val);        // Updating left child
updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
tree[node] = tree[node*2] + tree[node*2+1];        // Updating root with max value
}

int queryRange(int node, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return 0;         // Out of range
if(lazy[node] != 0)
{
// This node needs to be updated
tree[node] += (end - start + 1) * lazy[node];            // Update it
if(start != end)
{
lazy[node*2] += lazy[node];         // Mark child as lazy
lazy[node*2+1] += lazy[node];    // Mark child as lazy
}
lazy[node] = 0;                 // Reset it
}
if(start >= l and end <= r)             // Current segment is totally within range [l, r]
return tree[node];
int mid = (start + end) / 2;
int p1 = queryRange(node*2, start, mid, l, r);         // Query left child
int p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
return (p1 + p2);
}

the (end-start + 1) * val) is not related to the concept of lazy propagation in segment trees in a general case but to a particular application, additive operation on the nodes. What are you trying to learn or apply the structure for?
Iâ€™m not avoiding an answer, but I would like to be sure of what you are asking. The title remarks â€śconceptâ€ť but then a particular implementation arises.

1 Like

Lazy Propagation is basically used in range update queries. Since you cannot update whole interval in logN time. You only update the node when itâ€™s needed thatâ€™s why it named lazy.

Now each node contains a value for some range ( start, end). Thatâ€™s why to update itâ€™s value we do (end-start+1)*val.

1 Like

What to do if i am maintaining a â€śsetâ€ť at each node which stores the values in that range of node.
Now while updating, instead of doing ((end-start+1)*val) what will I do, for updating in the set efficiently? The question is when i m doing range updates, what all to do if I am maintaining a set at each node for some pupose . Thanks in advance!

@posiedon99: The concept is very simple. You donâ€™t apply changes to the range immediately unless or until it is necessary.

When there is a query that asks for the range which you updated previously, then It will propagate the needed value up to the layer where your current query goes.

PS: There is no point in updating the range If you donâ€™t want the answer for that query in the future.

I hope it makes things a bit clearer for you.

1 Like

Bro, the topic came in the recent discussion because of my question in this thread Can you please answer that

what your updating function should do? Are you replacing the whole range with the same value? If thatâ€™s the case your set will contain just this value.

I am adding a value (say x) to all the elements of a range.

It might be easier to help you if you explain what youâ€™re trying to do or share the statement of the problem you are trying to solve.
From your last message I undersand that your updates consist of adding some integer to all numbers of a given range, right? What kind of queries you have to answer? What about the initial values of the elements, are all 0s or not? What are the constraints?