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 adding 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
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[] with n elements and q queries 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:
So 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:
: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 M the 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 that a + b ≠ b + a). Informally, we can think of + as string concatenation. For convenience, we also require that M contains a unit element — an element e that e + x = x + e = x for any x in M. Such a set M (with an associative binary operation and a unit) is called a monoid. Examples of monoids are:
To summarize:
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 a may have multiple representations as a segment tree. For example, let the array contain integers with addition, and fk be the operation 'add k to all elements of the sub-array'. We write each node of a tree as a pair (fk, s), where s is the sum of the sub-array and fk is the pending operation. We write the whole tree as a sequence of nodes [(fk1, s1), (fk2, s2), ...] 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 array a = [4, 5] may be represented by the following trees:
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 value s once we apply operation f to the sub-array. In other words, we need the function applyAggregate: F × M → M satisfying applyAggregate(f, concat(a[i..j])) = concat(f(a[i..j])). For our example we have applyAggregate(fk, s) = s + k × L, where L is the length of the sub-array.
This is not all, though. Consider the tree T = [(f1, 9), (f2, 2), (f0, 5)]. If we calculate the aggregate value at (f2, 2) as 2 + 2 × 1 = 4, it will be wrong. The problem is, there is another operation pending on this sub-array — f1 (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(T2) = T3, where T2 and T3 are defined above. (Note how the aggregated value at the parent is changed by applyAggregate function.)
The children, however, may have their own pending operations. So when we 'push' an operation from the parent, we actually have to compose it with the existing operation in the child. We finally arrive at the second function required for lazy propagation: compose: F × F → F, where compose(child, parent) is the new operation at child after 'pushing' from parent.
To summarize, the only functions we need to implement are:
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 inside a[i..j], apply it to the whole node and stop the recursion. (And when current sub-array doesn't intersect a[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
andcompose
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.
Dear sir, it really helped me understand abstract version of lazy segtree. I know you wrote it 7 years ago, but I had to express my gratitude. Thank you so much.