Range Operations: Lazy Propagation

A segment tree is one of the most powerful tree data structures which enables one to answer queries over an array and update the array in minimum time. It is implemented as a binary tree (two children) that stores the resultant values.

Segments work great with point updates, but in many scenarios, we have to update the values in the given range from l to r, like replace or increment all elements in the range. Though we can do it using a segment tree it would cost us complexity up to O(N*logN) updating every element at a time. For handling situations like this, lazy propagation comes in handy.

Lazy propagation is a range update and query optimized implementation of a segment tree that performs both operation O(logN) time.

*In short, as the name suggests, the algorithm works on laziness for what is not important at the time. Don’t update a node until needed, which will avoid the repeated sharing. *

Let’s consider an array A of length N on which we are going to perform range operation and a segment tree, seg length 4*N,  to store the values of the segment tree.

Basic terminology:

• The root node is always present at seg[0] or 0th index and represents the whole array A[1,…, N]

• Child of node at i are present at 2*i (left) and 2*i+1 (right)

• Leaf nodes of segment tree represent every value of A

Building a segment tree:

Building a segment tree for lazy propagation works the same as a basic segment tree, as lazy propagation works only for range operation.

We will simply backtrack from every leaf to the parent updating the parent with the values of the left and right child.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void build(int node, int st, int en) {
  if (st == en) {
    // left node ,string the single array element
    seg[node] = arr[st];
    return;
  }

  int mid = (st + en) / 2;

  // recursively call for left child
  build(2 * node, st, mid);

  // recursively call for the right child
  build(2 * node + 1, mid + 1, en);

  // Updating the parent with the values of the left and right child.
  seg[node] = seg[2 * node] + seg[2 * node + 1];
}

Above, every node represents the sum of both subtrees below it. Build function is called once per array, and the time complexity of build() is O(N).

Below is a segment tree representation of example array A {1,3,5,7,9,11}

Credits for the image go to Kapilgarg.

Updating the segment tree:

In point update, we update the leaf of the segment tree and recursively update the parents corresponding to the leaf. We try to implement the same while updating a range. Suppose we have to update a node X, we make the updates to X only and notify both the children that they are to update in future, for having this functionality and we store the records in another binary tree lazy which has the same structure as seg. We initialize the lazy array with 0, which denotes that there are no pending updates, and non-zero values represent pending updates, so wherever we come across nodes with non-zero lazy values we make the updates to that and inform the child nodes for the same update.

Cases while updating

1. Segment lies outside the query range: in this case, we can just simply return back and terminate the call.

2. Segment lies fully inside the query range: in this case, we simply update the current node and mark the children lazy.

3. If they intersect partially, then we all update for both the child and change the values in them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void update(int node, int st, int en, int l, int r, int val) {
  if (lazy[node] != 0) // if node is lazy then update it
  {
    seg[node] += (en - st + 1) * lazy[node];

    if (st != en) // if its children exist then mark them lazy
    {
      lazy[2 * node] += lazy[node];
      lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0; // No longer lazy
  }
  if ((en < l) || (st > r)) // case 1
  {
    return;
  }
  if (st >= l && en <= r) // case 2
  {
    seg[node] += (en - st + 1) * val;
    if (st != en) {
      lazy[2 * node] += val; // mark its children lazy
      lazy[2 * node + 1] += val;
    }
    return;
  }

  // case 3
  int mid = (st + en) / 2;

  // recursively call for updating left child
  update(2 * node, st, mid, l, r, val);
  // recursively call for updating right child
  update(2 * node + 1, mid + 1, en, l, r, val);

  // Updating the parent with the values of the left and right child.
  seg[node] = (seg[2 * node] + seg[2 * node + 1]);
}

Congrats, we have become lazy now! 😜

Query on Segment Tree

We don’t have to do much while doing a query for an interval. It is the same as updating: checking if the current node is lazy, if it marks its child nodes lazy if they exist, and updating the current node, then returning the node value.

Cases while querying

1. Segment lies outside the query range: in this case, we can just simply return 0 and terminate the call.

2. Segment lies fully inside the query range: in this case, we simply return the current node.

3. If they intersect partially, then we all query for both the child and return the sum of their values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int query(int node, int st, int en, int l, int r) {
  /*If the node is lazy, update it*/
  if (lazy[node] != 0) {

    seg[node] += (en - st + 1) * lazy[node];
    if (st != en) //Check if the child exist
    {
      // mark both the child lazy
      lazy[2 * node] += lazy[node];
      lazy[2 * node + 1] += lazy[node];
    }
    // no longer lazy
    lazy[node] = 0;
  }
  // case 1
  if (en < l || st > r) {
    return 0;
  }

  // case 2
  if ((l <= st) && (en <= r)) {
    return seg[node];
  }
  int mid = (st + en) / 2;

  //query left child 
  ll q1 = query(2 * node, st, mid, l, r);

  // query right child
  ll q2 = query(2 * node + 1, mid + 1, end, l, r);

  return (q1 + q2);
}

Conclusion

Both segment trees and lazy propagation deal with a great variety of questions and both can do range queries in O(logN).

Problems on lazy propagation for practice

Adit and the Tree

Range Updates and Sums (Similar to one discussed above)

Range Queries and Copies