Segment Tree Introduction 🎯

Welcome to our deep dive into the world of Segment Trees! In this lesson, we'll learn about this powerful data structure that helps solve problems efficiently, especially those related to range queries and updates. Let's get started!

What is a Segment Tree? 📝

A Segment Tree is a data structure used to efficiently solve range queries and updates on an array. It divides the original array into smaller segments (ranges) and stores the cumulative sum or other useful information for each segment and its sub-segments.

Why use a Segment Tree? 💡

Segment Trees are essential for solving problems that involve range queries (e.g., finding the sum of elements within a specific range) and updates (e.g., changing the value of multiple elements in the same range). They offer O(log n) time complexity for both range queries and updates, making them incredibly efficient compared to the O(n) time complexity of naive solutions.

Building a Segment Tree 📝

To build a Segment Tree, follow these steps:

Divide the original array into segments of equal size (or based on the range of the problem).
Create a Segment Tree with the same number of nodes as the segments in the original array. Each node in the Segment Tree represents a segment in the original array.
Store the cumulative sum or other useful information for each segment and its sub-segments in the Segment Tree.

Segment Tree Operations 📝

Segment Trees support two main operations:

Range Query: Calculate the cumulative sum or other useful information for a specific range in the original array.
Update: Change the value of multiple elements in the same range of the original array.

Segment Tree Types 💡

Segment Trees can be categorized into two main types:

Lazy Propagation Segment Tree: A Segment Tree that uses a "lazy" flag to store pending updates, allowing the tree to efficiently update multiple elements in the original array without the need for explicit update operations.
Non-Lazy Segment Tree: A Segment Tree that does not use a "lazy" flag and requires explicit update operations for updating multiple elements in the original array.

Example: Segment Tree with Lazy Propagation 📝

Let's build a Segment Tree with Lazy Propagation to solve a problem.

python

class SegmentTree:
    def __init__(self, arr, n):
        self.n = n
        self.size = 4 * n
        self.arr = [0] * self.size
        self.build(arr, 0, 0, n)

    def build(self, arr, idx, ss, se):
        if ss == se:
            self.arr[idx] = arr[ss]
            return
        mid = (ss + se) // 2
        self.build(arr, 2 * idx + 1, ss, mid)
        self.build(arr, 2 * idx + 2, mid + 1, se)
        self.arr[idx] = self.arr[2 * idx + 1] + self.arr[2 * idx + 2]

    def update(self, idx, ss, se, i, val, lazy=0):
        if i < ss or i > se:
            return
        if ss == se:
            self.arr[idx] = val
            return
        mid = (ss + se) // 2
        self.propagate(2 * idx + 1, ss, mid, lazy)
        self.propagate(2 * idx + 2, mid + 1, se, lazy)
        self.arr[idx] = self.arr[2 * idx + 1] + self.arr[2 * idx + 2]

    def propagate(self, idx, ss, se, lazy):
        if lazy != 0:
            self.arr[idx] += lazy * (se - ss + 1)
            if ss != se:
                self.arr[2 * idx + 1] += lazy
                self.arr[2 * idx + 2] += lazy
            lazy = 0
        self.arr[idx] = self.arr[2 * idx + 1] + self.arr[2 * idx + 2]

    def query(self, ss, se, iq, ie):
        if iq <= ss and se <= ie:
            return self.arr[0]
        if ss >= iq and ie >= se:
            return self.arr[0]
        mid = (ss + se) // 2
        res1 = self.query(2 * idx + 1, mid + 1, iq, ie)
        res2 = self.query(2 * idx + 2, mid + 1, iq, ie)
        return res1 + res2

# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
seg_tree = SegmentTree(arr, len(arr))
seg_tree.update(0, 0, len(arr) - 1, 5, 20)
print(seg_tree.query(0, len(arr) - 1, 2, 6))  # Output: 25

Quiz 🎯

That's all for this lesson! You've learned about the Segment Tree data structure and how it can help you solve range queries and updates efficiently. Happy coding! 💡