Komyona_neko's blog

By Komyona_neko, history, 8 years ago, In English

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

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:

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.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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:

    1. sum+=(((R — L + 1) * (R — L + 2) / 2) * K)
    2. left_child.ft+=K, left_child.cd+=K
    3. right_child.ft+=(MID-L+2)*K, right_child.cd+=K
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    :XD

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry for necroposting, but what does the variable 'val' mean in your code? I tried implementing your solution, and I succeeded but I didn't use 'val', so is 'val' just always 0 in your code? Also, is 'prog' just the value of K for each update? Thanks!

»
8 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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:

  • The set of strings with concatenation; unit is the empty string.
  • The set of integers with addition; unit is zero.
  • The set of residues modulo arbitrary number N with modular multiplication; unit is 1.

To summarize:

  • We have a (virtual) array a containing elements of a monoid M.
  • The array is represented by a binary tree. Each node of the tree corresponds to a sub-array a[i..j] and contains the value ai + ... + aj, which we also denote by concat(a[i..j]).
  • To change a single element in the array, traverse the tree down to the corresponding leaf, change the value at the leaf and finally go back to the root recalculating all aggregated values on the path (by concatenating the aggregated values at children).

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:

  • T1 = [(f0, 9), (f0, 4), (f0, 5)]
  • T2 = [(f2, 5), (f0, 2), (f0, 3)]
  • T3 = [(f0, 9), (f2, 2), (f2, 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 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:

  • applyAggregate(op, currentAggregate) = newAggregate
  • compose(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 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'.

struct F1 {     // Represents aggregate operation
    int L, R;   // applied at sub-array a[L..R]
    int add;    // add this to all elements

    int applyAggregate(int oldAggregate) {
        return oldAggregate + add * (R - L + 1);  // add to each of R-L+1 elements
    }

    void compose(const F1& parent) {  // compose in-place
        add += parent.add;
    }
};

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

struct F2 {     // Represents aggregate operation
    int L, R;   // applied at sub-array a[L..R]
    int v;      // change all elements to v; by convention, v == -1 means no change

    int applyAggregate(int oldAggregate) {
        if (v == -1) return oldAggregate; // no change
        return v * (R - L + 1);           // each of R-L+1 elements is set to v
    }

    void compose(const F2& parent) {  // compose in-place
        // if parent is changed, we change to the same value too; otherwise stay the same
        if (parent.v != -1) {
            v = parent.v;
        }
    }
};

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])

struct F3 {     // Represents aggregate operation
    int L, R;   // applied at sub-array a[L..R]
    int v;      // First, change all elements to v; by convention, v == -1 means no change
    int c;      // Second, multiply all elements by c
    int k, a;   // Third, add a to the first element, a+k to the second, a+2k to the third etc

    int applyAggregate(int oldAggregate) {
        int result = oldAggregate;
        // replace
        if (v != -1)
            result = v * (R - L + 1);

        // multiply
        result *= c;

        // add progression
        result += (R-L+1) * (2*a + (R-L)*k) / 2; // sum of progression

        return result;
    }

    void compose(const F3& parent) {  // compose in-place
        // replace
        if (parent.v != -1) {
            v = parent.v;
            c = 1;
            k = a = 0;
        }

        // multiply
        c *= parent.c;
        k *= parent.c;
        a *= parent.c;

        // add progression
        int newA = parent.a + parent.k * (L - parent.L); // the progression restricted to [L,R] starts with this number
        k += parent.k;
        a += newA;
    }
};

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is really helpful, thanks for spending time sharing this to us.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Best explanation of Lazy Propagation.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    16 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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.