#### I have started to solve some Segment Tree problems recently and I had some queries about the Lazy Propagation Technique.

I understand the basic concept of Lazy Propagation and have solved some problems (all of them in the format : **Add** v to each element in the range [i,j] , Answer the sum , maximum/minimum element ,some info for elements in range [a,b]).

I got the concept for the **add**ing element Lazy Propagation . But I have some confusion about **changing** the elements to v for all elements in the range [i,j] problem .

My question is , what is the general concept that I should have in mind while finding solution for these and more harder variations? I have seen lots of code online but they are mostly for the first version of the problem which I think I understand but I just don't know how to apply this concept to solve other variation of Lazy propagation problem.

And I also need some tips on debugging Segment tree problems.Thanks

Auto comment: topic has been updated by Komyona_neko (previous revision, new revision, compare).The main idea is that you need to think for an update of a node which can be done in O(1) time.

For example if you have the following problem:

Given an array

a[]withnelements andqqueries of the following types:1) Add an arithmetic progression to all nodes in range [L; R]. It's defined by L, R, K.

For example:

Array: 5 4 6 8 8 L = 1; R = 3; K = 2;

This means we should increase A[1] with K, A[2] with 2 * K and A[3] with 3 * K. I think you should understand this type of query (Or should I call it update).

2) Output the sum of all numbers in range [L; R]. It's defined just by L and R.

NOW THINK ABOUT HOW WOULD YOU SOLVE THIS FOR A BIT.So it is obvious that we will use a segment tree with lazy propagation. The main fact here is that we will need two "lazy values". One for the arithmetic progression value and the other for the fixed sum adding.

Then if we have a node in our segment tree which covers [L; R] how can we add an AP with value K to it?

We will simply add

`(((R - L + 1) * (R - L + 2) / 2) * lazy_ap)`

to the total sum. But then how can we add the lazy to the left and right half of the node?Here comes the next observation:

Lets get the middle (MID) of our range (

`MID = (L + R) / 2`

)Then we can simply increase

[L; MID]'s lazy_ap by[L; R]'s lazy_ap.But it's not the same for

[MID + 1; R].`ADD_SUM[MID + 1; R] = K * (MID - L + 1) + K * (MID - L + 2) + ... + K * (R - L + 1)`

`but ADD_SUM[MID + 1; R] = K * (1) + K * (2) + ... + K * (R - MID) + (MID - L) * K`

So this means that we increase the basic lazy of

[MID + 1; R]by K and the lazy_ap also by K.And here is the code:

CodeSo the thing I want to tell is that you need an easy way of doing the update of a node just by knowing the lazy value/values. You can try finding some problems with segment tree + lazy. There should be a lot of them. After solving about 5-6 of them you should be able to solve this type of problems. And also don't copy-paste your segment tree code. If you write it every time and then debug it you should be able to write a segment tree without debugging.

PS:I didn't mention about the problem for changing all element in a range so. The main fact here is that we again need to change the sum of a node just by the lazy. Let our lazy be the that we have changed all elements to in the current node. Then the new sum will equal to (R — L + 1) * lazy. And we also need to overwrite the lazy of the current node's children (halves). If you have understood the problem I gave you, you should have came up with a solution. If you haven't come with a solution, reread the explanation.Since adding two or more APs also gives us another AP, we can perform the update in following way also:

let a node in segment tree (which covers a range L to R) store three values:

sum :the current sum of values in L to R

ft :the first term of AP to be added to this node

cd :common difference of AP to be added to this node

Now to add an AP with value K, we have to do:

can you help me here I am facing difficulty in implementing what you suggested . I wish I can see your code.

:XD

Just wait 2 more days, you'll get to know how to solve CHONQ

just saying, you could have written an entire blog on it. XD

Implementing harder variations of lazy propagation becomes extremely easy once you abstract away all unnecessary clutter and focus only on important details.

Denote by

Mthe type of elements that are stored in the array that our segment tree represents. Nodes of the tree correspond to sub-arrays and contain aggregated information about the elements of this sub-array. The aggregation is represented by a binary operation that we denote by + . This operation must be associative (a+ (b+c) = (a+b) +c), but not necessarily commutative (it may be thata+b≠b+a). Informally, we can think of + as string concatenation. For convenience, we also require thatMcontains aunit element— an elementethate+x=x+e=xfor anyxinM. Such a setM(with an associative binary operation and a unit) is called amonoid. Examples of monoids are:Nwith modular multiplication; unit is 1.To summarize:

acontaining elements of a monoidM.a[i..j] and contains the valuea_{ i}+ ... +a_{ j}, which we also denote byconcat(a[i..j]).Let's move on to aggregate operations. The basic idea is that each node of the tree, in addition to the aggregate value on the corresponding sub-array, will contain an operation that is supposed to be applied to the sub-array as a whole. We denote the set of all possible operations by

F.Note that now the same array

amay have multiple representations as a segment tree. For example, let the array contain integers with addition, andf_{ k}be the operation 'addkto all elements of the sub-array'. We write each node of a tree as a pair (f_{ k},s), wheresis the sum of the sub-array andf_{ k}is the pending operation. We write the whole tree as a sequence of nodes [(f_{ k 1},s_{1}), (f_{ k 2},s_{2}), ...] in top-down order, so the first node represents the whole array, the second node represents the left half of the array, the third node — the right half, the fourth node — the first quarter and so on. Then the arraya= [4, 5] may be represented by the following trees:T_{1}= [(f_{0}, 9), (f_{0}, 4), (f_{0}, 5)]T_{2}= [(f_{2}, 5), (f_{0}, 2), (f_{0}, 3)]T_{3}= [(f_{0}, 9), (f_{2}, 2), (f_{2}, 3)]and so on.

Let's think about what we need from operations

F. What we really want is still the actual aggregated values on sub-arrays. So when we have a node (f,s), we need to find what will happen to the aggregated valuesonce we apply operationfto the sub-array. In other words, we need the functionapplyAggregate:F×M→MsatisfyingapplyAggregate(f,concat(a[i..j])) =concat(f(a[i..j])). For our example we haveapplyAggregate(f_{ k},s) =s+k×L, whereLis the length of the sub-array.This is not all, though. Consider the tree

T= [(f_{1}, 9), (f_{2}, 2), (f_{0}, 5)]. If we calculate the aggregate value at (f_{2}, 2) as 2 + 2 × 1 = 4, it will be wrong. The problem is, there isanotheroperation pending on this sub-array —f_{1}(it is applied to the whole array, and hence to the sub-array too). We need to make sure this doesn't happen.For this purpose, each time we descend from a parent to a child in the tree, we replace the operation in the parent with two operations in its children (this is known as 'push' operation). The result is a tree that represents the same array, but doesn't have the problem described in the previous paragraph. For example,

push(T_{2}) =T_{3}, whereT_{2}andT_{3}are defined above. (Note how the aggregated value at the parent is changed byapplyAggregatefunction.)The children, however, may have their own pending operations. So when we 'push' an operation from the parent, we actually have to

composeit with the existing operation in the child. We finally arrive at the second function required for lazy propagation:compose:F×F→F, wherecompose(child,parent) is the new operation at child after 'pushing' from parent.To summarize, the only functions we need to implement are:

applyAggregate(op,currentAggregate) =newAggregatecompose(childOp,parentOp) =newChildOp.Applying an operation on sub-array

a[i..j] is similar to calculating the sum (concatenation) on this sub-array: descend the tree recursively, but when current sub-array is completely insidea[i..j], apply it to the whole node and stop the recursion. (And when current sub-array doesn't intersecta[i..j], stop the recursion too.)We now implement these functions for three examples. All examples work with the same element monoid — integers with addition — but have different aggregate operations.

1. Aggregate operation is 'add the same number to all elements'.

2. Aggregate operation is 'change all elements to the same number'.

3. Now for a complicated example, aggregate operations are: 'change all elements to the same number'; 'multiply all elements by the same number'; 'add an arithmetic progression to the sub-array' (e.g., [1,1,1,1] becomes [2,4,6,8])

The above code excerpts are the only thing that distinguishes the three segment trees. The rest of the implementation uses`applyAggregate`

and`compose`

functions; it is identical in trivial cases (1), (2) and the complicated case (3). This shows that there is no conceptual difference between these cases.tl;dr:Decomposing the problem by formulating generic requirements leads to better understanding and cleaner, simpler, more general implementation. See also:Elements of Programming. Alexander Stepanov and Paul McJones.Update: See source code here.This is really helpful, thanks for spending time sharing this to us.

Could you please provide a code with the above structs ? I'm a bit confused about how to use them.

Added source code here.

Best explanation of Lazy Propagation.

@slycelote Well, this does is really helpful and of course, extremely beautiful explanation too. I'd be really thankful if you(or anyone else) could explain the compose function a little more. A little more insight into it, about how it is called from main(), a little explanation about the code too will be really appreciated.

Added source code here, maybe this will help.

:)