enjoyalgorithms

Segment Tree Part 2 (Point and Range Update, Lazy Propagation)

Introduction

In the previous blog, we discussed the construction of a segment tree and range query operations on an array. Now, we want to update either a single element or a range of the original array. In this blog post, we will learn how to use segment trees for efficient point and range updates.

  • For the point update query, update(idx, val), we need to increment the element at index idx in the original array by val, i.e., arr[idx] = arr[idx] + val.
  • For the range update query, update(l, r, val), we need to increment all the elements from index l to r in the original array by val.

Let's begin this discussion with the question of finding the range sum. Suppose you have an array arr[] of size n, and you need to find the sum of values in a given range [l, r].

One idea would be to sum all the values in the range [l, r] and return the sum. In this scenario, the time complexity will be O(r - l), which will be O(n) in the worst case. If there are p such range sum queries, the overall time complexity will be O(pn) in the worst case.

Another good idea is that if we know the sum of prefixes from [0 to r] and [0 to l - 1], we can easily find the sum of the range from [l, r]. Here is the formula: Sum[l, r] = Sum[0, r] - Sum[0, l - 1]. To achieve this, we can convert the array into a prefix sum array in O(n) time and perform every range sum operation in O(1) using the above formula. If there are p range sum queries, the overall time complexity is O(n) + p * O(1) = O(n + p).

However, what would be the issue with the prefix sum approach? If array values change frequently, we need to reconstruct the prefix sum array with every change. If we want to change arr[i] to arr[i] + x, we must add x to every value from index i to n - 1 to reconstruct the prefix sum array. Therefore, every update in a value will take O(n) time in the worst case.

So, if there are frequent range sum queries and values are updated frequently, we can use a segment tree to perform point updates and range sum query operations in O(log n) time. We have previously discussed the range minimum query on the segment tree in a previous blog. You can easily modify that code for range sum queries. In this blog, we will discuss point and range update methods on segment trees.

Point Updates in Segment Trees

Recall that we learned how to build a segment tree in the last blog. We observed that each node in a segment tree represents a range from the array, and the leaf nodes of the segment tree represent individual indices.

To perform a point update, you should start by updating the appropriate leaf node in the segment tree. Afterwards, you can propagate this update toward the root, level by level, by updating the parent nodes. Since each level divides the array segment into two parts, there will be only one node at each level that needs updating. Therefore, at most O(log n) nodes need to be updated.

We can implement the update function recursively. To do this, we initially pass the root of the tree to the function. The function then recursively calls itself with one of the two child nodes (the one that contains the node to be updated within its range), and it recomputes its sum value, similar to the build method of the segment tree.

We can define a function update(int segTree[], int arr[], int node, int start, int end, int idx, int val) that takes these values as input parameters:

  • segTree[]: the segment tree array.
  • arr[]: the input array.
  • node: the index of the current node in the segment tree.
  • start, end: the start and end indices of the nodes represented by the current node.
  • idx: the index in the array that needs to be updated.
  • val: the value by which the element needs to be incremented.

Pseudocode: Point update on segment tree

void update(int segTree[], int arr[], int node, int start, int end, int idx, int val) 
{
    // Leaf node, update directly
    if (start == end) 
    {
        arr[idx] = val
        segTree[node] = val
    } 
    
    else 
    {
        int mid = start + (end - start) / 2
        
        if (start <= idx && idx <= mid) 
            update(segTree, arr, 2 * node, start, mid, idx, val) // Recurse on the left child
        else
            update(segTree, arr, 2 * node + 1, mid + 1, end, idx, val) // Recurse on the right child
        
        // Update the current node with the sum of its children
        segTree[node] = segTree[2 * node] + segTree[2 * node + 1])
    }
}

Range Update in Segment Trees

Sometimes, problems require updating an interval from l to r instead of a single element. A Segment Tree allows the application of modification queries to an entire segment of contiguous elements in O(logn) time.

In the brute force approach, we update all the elements in the range and construct the prefix sum array again, which takes O(n) time. Another solution using a Segment Tree with point updates is to update all the elements one by one. The complexity of this approach will be O(n) per range update operation, and updating a single element takes O(logn) time. So, the overall complexity becomes O(nlogn), which is worse than the prefix sum array approach.

Lazy Propagation in Segment trees

As we know, a node in the segment tree stores a query's value for a range of indexes. If a node's range lies within the range of the update operation, then we need to update all descendants of that node. So, to improve on our last approach, we become lazy, i.e., we will do work only when required. When there is a need to update an interval, we will update the node in the segment tree, mark child nodes that require an update, and update them when needed.

With the Lazy propagation idea, we update the node and postpone updates to its children by storing this update information in a separate array called lazyTree[] with the same size as the segment tree. All the elements inside this array are initially zero, representing that we do not have any updates pending on node i in the segment tree. Similarly, a non-zero value of lazyTree[i] represents that this much value needs to be updated to node i in the segment tree before making any query operation.

Here are the considerations we need to make before performing a range update in the segment tree:

  1. If a node has any pending updates, we should first apply those pending updates to the current node.
  2. When we encounter a node whose range lies entirely within the given update range, we should update the current node and mark the corresponding entries in the lazyTree[] for its child nodes. This approach is known as the "lazy" approach because it minimizes the work required to obtain the correct answer. We address updating the remaining affected nodes when necessary.
  3. If the update range overlaps with the range represented by the current node, we should update the node in a manner similar to the point update function.

We define a function called updateRange(int segTree[], int arr[], int lazyTree[], int node, int start, end, int l, int r, int val), which takes the following input parameters:

  • segTree[]: the segment tree array.
  • arr[]: the input array.
  • lazyTree[]: the lazy tree array that stores information about pending updates, initialized to zero initially.
  • node: the index of the current node in the segment tree.
  • start and end: the start and end indices of the nodes represented by the current node.
  • l and r: the left and right indices from the array that need to be updated.
  • val: the value by which each element within the range should be incremented.

Pseudocode: Range update on segment tree using lazy propagation

void updateRange(int segTree[], int lazyTree[], int node, 
                                int start, int end, int l, int r, int val) 
{
    // Check if there are pending updates for the current node
    if (lazyTree[node] != 0) 
    {
        // Apply the pending update to the current node
        segTree[node] += (end - start + 1) * lazyTree[node]
        // If the current node is not a leaf node, propagate the update to its children
        if (start != end) 
        {
            lazyTree[node * 2] += lazyTree[node]
            lazyTree[node * 2 + 1] += lazyTree[node]
        }   
        // Reset the pending update for the current node
        lazyTree[node] = 0
    }
    
    // If the range represented by the current node does not overlap with the update range
    if (start > end || start > r || end < l)
        return
    
    // If the range represented by the current node completely overlaps with the update range
    if (start >= l && end <= r) 
    {
        // Apply the update to the current node
        segTree[node] += (end - start + 1) * val       
        // If the current node is not a leaf node, propagate the update to its children
        if (start != end) 
        {
            lazyTree[node * 2] += val
            lazyTree[node * 2 + 1] += val
        }
        return
    }
    
    // If the range represented by the current node partially overlaps with the update range
    int mid = start + (end - start) / 2 
    // Recursively update the left and right children
    updateRange(segTree, lazyTree, node * 2, start, mid, l, r, val)
    updateRange(segTree, lazyTree, node * 2 + 1, mid + 1, end, l, r, val)
    // Update the current node based on the updated children
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1]
}

Now, we have to adjust our range query operation to account for the updates pending in the lazyTree array. For this, we need to update the relevant nodes during the range query operation for which updates are pending in the lazyTree. So, we must check if there is any pending update for this node. If there is one, we update it and set the value in the lazyTree to zero. Then, we proceed to find the answer to the query, just as before.

Pseudocode: Range query on segment tree using lazy propagation

int queryRange(int segTree[], int lazyTree[], int node, 
                              int start, int end, int l, int r) 
{
    // If the range represented by the current node does not overlap with the query range
    if (start > end || start > r || end < l)
        return 0
    
    if (lazyTree[node] != 0) 
    {
        segTree[node] += (end - start + 1) * lazyTree[node]     
        // If the current node is not a leaf node, propagate the update to its children
        if (start != end) 
        {
            lazyTree[node * 2] += lazyTree[node]
            lazyTree[node * 2 + 1] += lazyTree[node]
        }    
        // Reset the pending update for the current node
        lazyTree[node] = 0
    }
    
    // If the range represented by the current node completely overlaps with the query range
    if (start >= l && end <= r)
        return segTree[node]
    
    // If the range represented by the current node partially overlaps with the query range
    int mid = start + (end - start) / 2
    int p1 = queryRange(segTree, lazyTree, node * 2, start, mid, l, r)
    int p2 = queryRange(segTree, lazyTree, node * 2 + 1, mid + 1, end, l, r)
    // Combine the results and return
    return (p1 + p2)
}

Time complexity of lazy propagation

The time complexity of lazy propagation is O(logn). Similar to the query operation, we claim that two nodes in each level are explored further at most. The proof is discussed in the previous blog.

We will keep updating this blog with more insights later. Please share your feedback or insights. Enjoy learning, Enjoy algorithms!

More from EnjoyAlgorithms

Self-paced Courses and Blogs