Lazy Segment Tree

Lazy Segment Tree is a data structure that allows efficient range queries and updates on an array or a list. It extends the functionality of the Segment Tree by introducing a lazy propagation technique to optimize updates on a range of elements.

In a traditional Segment Tree, updates and queries are performed by traversing the tree from the root to the leaf nodes. However, for certain types of queries and updates, this approach can be inefficient, especially when dealing with large arrays.

The Lazy Segment Tree addresses this issue by postponing the updates to a later stage, known as lazy propagation. Instead of updating every node in the path from the root to the leaf, the Lazy Segment Tree stores the pending updates in a separate array or data structure. These updates are then applied during subsequent queries or when needed.

Here's a general outline of the Lazy Segment Tree implementation and its operations:

Build: Construct the Lazy Segment Tree from an initial array or list of elements. This operation builds the tree recursively by dividing the array into segments and assigning values to the tree nodes.
Query: Perform a range query operation on the Lazy Segment Tree. This operation returns the result of a specified function or operation applied to a given range of elements in the array.
Update: Modify the elements in a specific range of the array. This operation updates the Lazy Segment Tree and marks the corresponding nodes as pending updates without actually modifying the values immediately.
Lazy Propagation: Apply the pending updates to the relevant nodes of the tree when required, typically during a query or another update operation. This process ensures that the tree remains accurate and reflects the latest changes made to the array.

A question that can be solved using the Lazy Segment Tree concept is "Range Sum Query - Mutable

Problem Statement: Given an integer array nums, handle multiple queries of the following types:

Update: Modify the element at index i to a new value.
Sum Range: Calculate the sum of all elements within the range [left, right] inclusive.

Example:

# Class definition for the LazySegmentTree
class LazySegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        self.lazy = [0] * (2 * self.n)

        # Build the initial tree
        self.build(nums, 0, self.n - 1, 1)

    def build(self, nums, left, right, idx):
        if left == right:
            self.tree[idx] = nums[left]
            return

        mid = (left + right) // 2
        self.build(nums, left, mid, 2 * idx)
        self.build(nums, mid + 1, right, 2 * idx + 1)

        # Update the tree node with the appropriate value (e.g., sum)
        self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

    def update(self, left, right, value, idx, l, r):
        if self.lazy[idx] != 0:
            self.tree[idx] += (r - l + 1) * self.lazy[idx]

            if l != r:
                self.lazy[2 * idx] += self.lazy[idx]
                self.lazy[2 * idx + 1] += self.lazy[idx]

            self.lazy[idx] = 0

        if left > r or right < l:
            return

        if left <= l and right >= r:
            self.tree[idx] += (r - l + 1) * value

            if l != r:
                self.lazy[2 * idx] += value
                self.lazy[2 * idx + 1] += value

            return

        mid = (l + r) // 2
        self.update(left, right, value, 2 * idx, l, mid)
        self.update(left, right, value, 2 * idx + 1, mid + 1, r)

        # Update the tree node with the appropriate value (e.g., sum)
        self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

    def query(self, left, right, idx, l, r):
        if self.lazy[idx] != 0:
            self.tree[idx] += (r - l + 1) * self.lazy[idx]

            if l != r:
                self.lazy[2 * idx] += self.lazy[idx]
                self.lazy[2 * idx + 1] += self.lazy[idx]

            self.lazy[idx] = 0

        if left > r or right < l:
            return 0

        if left <= l and right >= r:
            return self.tree[idx]

        mid = (l + r) // 2
        left_sum = self.query(left, right, 2 * idx, l, mid)
        right_sum = self.query(left, right, 2 * idx + 1, mid + 1, r)

        # Return the result of the operation (e.g., sum)
        return left_sum + right_sum

# Example usage
nums = [1, 3, 5]
seg_tree = LazySegmentTree(nums)

# Update operation: Modify the element at index 1 to a new value 2
seg_tree.update(1, 1, 2, 1, 0, len(nums) - 1)

# Sum Range operation: Calculate the sum of elements in the range [0, 2]
range_sum = seg_tree.query(0, 2, 1, 0, len(nums) - 1)
print("Sum Range:", range_sum)
# Output: Sum Range: 8

In this example, we define a class LazySegmentTree that implements the Lazy Segment Tree data structure. The class contains methods for building the tree, updating elements, and querying ranges.

We create an instance of the LazySegmentTree class with an initial array [1, 3, 5]. The constructor builds the segment tree using the build method.

Next, we perform an update operation to modify the element at index 1 to a new value of 2 using the update method.

Finally, we perform a sum range query to calculate the sum of elements in the range [0, 2] using the query method.

The LazySegmentTree class maintains two arrays: tree for storing the segment tree nodes and lazy for storing the pending updates. The update and query methods use lazy propagation to optimize the operations. If a node has a pending update, it is applied before performing further operations.

The time complexity of updating and querying ranges in the Lazy Segment Tree is O(log n), where n is the number of elements in the input array. This is because the tree height is logarithmic with respect to the number of elements. The space complexity is O(n) to store the tree and lazy arrays.

Note: This example provides a general idea of how to implement and use a Lazy Segment Tree. The exact implementation and complexity may vary depending on the specific problem and requirements.

Let's solve the "Range Sum Query - Mutable" using a Lazy Segment Tree implementation. This problem involves designing a data structure that supports two operations: updating an element at a given index and calculating the sum of elements within a specified range.

Problem Statement: You are given an integer array nums and an object called NumArray, which is the implementation of the data structure.

Implement the NumArray class:

NumArray(int[] nums): Initializes the data structure with the given array nums.
void update(int index, int val): Updates the value of nums[index] to be val.
int sumRange(int left, int right): Returns the sum of the elements of the nums array in the range [left, right] inclusive.

Example:

class NumArray:

    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        self.lazy = [0] * (2 * self.n)

        # Build the initial tree
        self.build(nums, 0, self.n - 1, 1)

    def build(self, nums, left, right, idx):
        if left == right:
            self.tree[idx] = nums[left]
            return

        mid = (left + right) // 2
        self.build(nums, left, mid, 2 * idx)
        self.build(nums, mid + 1, right, 2 * idx + 1)

        # Update the tree node with the appropriate value (e.g., sum)
        self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

    def update(self, index, val):
        self.updateTree(index, val, 1, 0, self.n - 1)

    def updateTree(self, index, val, idx, left, right):
        if left == right:
            self.tree[idx] = val
            return

        mid = (left + right) // 2
        if index <= mid:
            self.updateTree(index, val, 2 * idx, left, mid)
        else:
            self.updateTree(index, val, 2 * idx + 1, mid + 1, right)

        # Update the tree node with the appropriate value (e.g., sum)
        self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

    def query(self, ql, qr):
        return self.queryRange(ql, qr, 1, 0, self.n - 1)

    def queryRange(self, ql, qr, idx, left, right):
        if self.lazy[idx] != 0:
            self.tree[idx] += (right - left + 1) * self.lazy[idx]

            if left != right:
                self.lazy[2 * idx] += self.lazy[idx]
                self.lazy[2 * idx + 1] += self.lazy[idx]

            self.lazy[idx] = 0

        if ql <= left and qr >= right:
            return self.tree[idx]

        if ql > right or qr < left:
            return 0

        mid = (left + right) // 2
        left_sum = self.queryRange(ql, qr, 2 * idx, left, mid)
        right_sum = self.queryRange(ql, qr, 2 * idx + 1, mid + 1, right)

        # Return the result of the operation (e.g., sum)
        return left_sum + right_sum

# Example usage
nums = [1, 3, 5]
num_array = NumArray(nums)

# Update operation: Modify the element at index 1 to a new value 2
num_array.update(1, 2)

# Sum Range operation: Calculate the sum of elements in the range [0, 2]
range_sum = num_array.query(0, 2)
print("Sum Range:", range_sum)
# Output: Sum Range: 8

In this example, we define a class NumArray that implements the "Range Sum Query - Mutable" problem using a Lazy Segment Tree data structure. The class contains methods for building the tree, updating elements, and querying ranges.

We create an instance of the NumArray class with an initial array [1, 3, 5]. The constructor builds the segment tree using the build method.

Next, we perform an update operation to modify the element at index 1 to a new value of 2 using the update method.

Finally, we perform a sum range query to calculate the sum of elements in the range [0, 2] using the query method.

The NumArray class maintains three arrays: tree for storing the segment tree nodes, lazy for storing the pending updates, and nums for storing the original array. The update and query methods utilize lazy propagation to optimize the operations. If a node has a pending update, it is applied before performing further operations.

Note: The given implementation assumes 0-based indexing for the array and ranges. If the problem statement specifies 1-based indexing, adjustments need to be made accordingly.

Lazy Segment Tree

DIFFICULTY

COMPANY

Data Structures