Lazy Propagation in Segment Tree : HORRIBLE

By Asim Krishna Prasad

---

Posted on 16/08/15
Tag : Data Structures

---

---

The question I am taking up is this HORRIBLE to try to make basics of Lazy Propagation in Segment Trees clear.
We are going to write two functions.
1> To update a given range

• Add a given 'val' to all the elements in the given range

2> To query a given range

• Get the sum of the elements in the given range

First of all let's try to understand the structure of segment tree we are going to use. We are going to use two arrays to store segment-tree (stree) and the lazy value (dirty).
We'll use 1-based indexing, so children of i-th node will be at (2*i) and ((2*i)+1).
To implement the lazy propagation, we need to follow these steps :

• Update a node only if it's completely inside the update-range, else update the lazy value and return.
• When querying, update all the nodes on the way with their lazy value and pass the lazy value to their children.

Let us define some variable names for ease :

• ql -> the left index of the query range (or update range).
• qr -> the right index of the query range (or update range).
• start -> the left index of the current range.
• end -> the right index of the current range.
• val -> the value to be added in the update function.

Now let us see some of the cases that we are going to encounter in the recursive approach.

1. The current-range is completely outside the query-range.
2. The current-range is completely inside the query-range.
3. The current-range is partially inside the query-range.

From the diagrams, it is clear that number of elements in the partial-overlap case is (min(qr,end) - max(ql,start) + 1).

The two functions will look like this :

The complete code will look something like this :


Hope it helps :)
Asim Krishna Prasad

---

COMMENTS :