Segment Trees

A Segment Tree is a data structure used for answering range queries efficiently. Segment Trees are particularly useful for problems that involve operations on intervals or ranges, like sum, minimum, maximum, or gcd queries over a range of array indices. Segment Trees allow for both efficient query operations and efficient updates, typically achieving O(log n) time complexity for both operations.

Basic Structure and Construction of Segment Tree

A Segment Tree is a binary tree where each node represents a range of elements. For an array of size ( n ), the segment tree will have approximately ( 2 n ) nodes, meaning its height is ( n ).

Construction of Segment Tree

To construct a Segment Tree, we:

1. Build a tree where each leaf node represents a single element from the array.
2. Each internal node represents a range (or segment) and stores the result of the operation (like sum or min) for that range.
3. For a node representing the range [l, r], we calculate its value by combining the values of its children, covering [l, mid] and [mid + 1, r].

Example Problem: Range Sum Query with Segment Tree

Consider an array arr where we want to efficiently calculate the sum of elements within any given range [l, r], as well as update an element in the array.

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (2 * self.n)
        self.build(arr)
    
    def build(self, arr):
        # Initialize leaf nodes
        for i in range(self.n):
            self.tree[self.n + i] = arr[i]
        
        # Build internal nodes by combining children
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def update(self, index, value):
        # Update leaf node
        index += self.n
        self.tree[index] = value
        
        # Update internal nodes
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]
    
    def query(self, left, right):
        # Adjust indices to leaf nodes
        left += self.n
        right += self.n
        sum_ = 0
        
        # Sum over the range
        while left <= right:
            if left % 2 == 1:
                sum_ += self.tree[left]
                left += 1
            if right % 2 == 0:
                sum_ += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
        return sum_

Explanation

1. Build: We initialize the leaves with array elements and calculate internal nodes by summing child nodes.
2. Update: Update a specific index and adjust its ancestors to reflect the new sum.
3. Query: Query the sum of a range [l, r] by traversing segments, adding the necessary elements, and moving up the tree.

Lazy Propagation

Lazy Propagation is a technique used with Segment Trees to make updates more efficient when we have range updates (e.g., incrementing all elements within a range by a certain value). Without lazy propagation, range updates would require updating multiple nodes repeatedly, increasing the time complexity.

With Lazy Propagation, we delay (or “lazily”) update nodes, marking them for future updates without applying them immediately. This reduces redundant updates and keeps the tree balanced.

Lazy Propagation: How It Works

Lazy Array: We maintain a separate lazy array where each node stores any pending update that needs to be applied to its children.

1. Update: When an update is called for a range, we:

• Mark the range as needing an update in the lazy array.
• Only apply the update to child nodes when necessary (when querying or performing another update that requires accessing those nodes).

1. Query: When querying a range, we check for any pending updates in the lazy array and apply them as we access each node, ensuring the query result is correct.

Example Code: Range Sum Update with Lazy Propagation

class SegmentTreeLazy:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)  # Segment tree
        self.lazy = [0] * (4 * self.n)  # Lazy array
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2 * node + 1, start, mid)
            self.build(arr, 2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def update_range(self, node, start, end, l, r, val):
        # Apply any pending updates to this node
        if self.lazy[node] != 0:
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:  # Not a leaf node
                self.lazy[2 * node + 1] += self.lazy[node]
                self.lazy[2 * node + 2] += self.lazy[node]
            self.lazy[node] = 0
        # Out of range
        if start > end or start > r or end < l:
            return
        # Current segment is fully within range [l, r]
        if start >= l and end <= r:
            self.tree[node] += (end - start + 1) * val
            if start != end:  # Propagate lazily to children
                self.lazy[2 * node + 1] += val
                self.lazy[2 * node + 2] += val
            return
        # Partially in range, continue to children
        mid = (start + end) // 2
        self.update_range(2 * node + 1, start, mid, l, r, val)
        self.update_range(2 * node + 2, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def query_range(self, node, start, end, l, r):
        # Apply any pending updates to this node
        if self.lazy[node] != 0:
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:  # Not a leaf node
                self.lazy[2 * node + 1] += self.lazy[node]
                self.lazy[2 * node + 2] += self.lazy[node]
            self.lazy[node] = 0
        # Out of range
        if start > end or start > r or end < l:
            return 0
        # Current segment is fully within range [l, r]
        if start >= l and end <= r:
            return self.tree[node]
        # Partially in range, continue to children
        mid = (start + end) // 2
        left_sum = self.query_range(2 * node + 1, start, mid, l, r)
        right_sum = self.query_range(2 * node + 2, mid + 1, end, l, r)
        return left_sum + right_sum

Explanation

1. Lazy Array: The lazy array stores pending updates for each node.
2. Update Range:

• If an update is within range, we mark the node’s children in the lazy array.
• If the current node only partially overlaps the update range, we propagate the update to children as needed.

1. Query Range:

• Apply any pending updates for the queried node.
• If the node’s range is fully within the query range, return its value.
• Otherwise, divide and query both children.

Applications of Segment Trees with Lazy Propagation

1. Range Sum Queries: Efficiently calculate sums over intervals of data.
2. Range Minimum/Maximum Queries: Find the minimum or maximum within a specified range.
3. Range Updates: Update all elements in a range without recalculating the entire range.
4. Interval Problems in Competitive Programming: Segment Trees are widely used in competitive programming for problems involving interval processing, such as range modifications.