Range Queries (Sum, Min, Max) 🎯

Welcome to our comprehensive guide on Range Queries! Today, we'll delve into the world of Sum, Min, and Max queries. These are fundamental techniques used in Data Structures and Algorithms that help us perform various operations on a set of numbers within a given range. Let's get started!

Understanding Range Queries 📝

Range Queries allow us to find the sum, minimum, and maximum values of a dataset within a specified range. These queries are particularly useful when dealing with large datasets where direct access is not feasible.

Why are Range Queries Important? 💡

Efficiency: Range Queries help us optimize our time complexity, making it possible to process large datasets quickly.
Flexibility: They allow us to retrieve specific information about a range of data, making it easier to analyze and visualize.
Real-world Applications: From financial calculations to game development, Range Queries have a wide range of practical applications.

Data Structures for Range Queries 💡

The most common data structures used for Range Queries are Segment Trees and Binary Indexed Trees (BIT). We'll focus on the Segment Tree in this lesson.

Segment Tree 📝

A Segment Tree is a binary tree data structure that enables us to perform various operations on a set of numbers efficiently. It divides the given range into smaller sub-ranges, allowing us to perform queries and updates in logarithmic time.

Implementing Range Sum Queries 💡

Let's implement a simple Range Sum Query using a Segment Tree.

python

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

    def build(self, arr, index, n):
        if n > 0:
            for i in range(n):
                self.tree[index + i] = arr[i]
            if n == 1:
                return
            self.build(arr, 2 * index, n // 2)
            self.build(arr, 2 * index + 1, n // 2)
            self.merge(index)

    def merge(self, index):
        self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

    def update(self, index, i, val, start, end, node):
        if i < start or end < i:
            return
        if start == end:
            self.tree[index] = val
        else:
            mid = (start + end) // 2
            self.update(2 * index, i, val, start, mid, node)
            self.update(2 * index + 1, i, val, mid + 1, end, node)
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

    def query(self, index, ss, se, qs, qe, node):
        if qs <= ss and se <= qe:
            return self.tree[index]
        if ss > qe or se < qs:
            return 0
        mid = (ss + se) // 2
        return self.query(2 * index, ss, mid, qs, qe, node) + self.query(2 * index + 1, mid + 1, se, qs, qe, node)

arr = [1, 3, 5, 7, 9]
seg_tree = SegmentTree(arr, len(arr))
print(seg_tree.query(1, 2, 4))  # Should output 13 (sum of elements from index 2 to 4)

Implementing Range Min and Max Queries 💡

To implement Range Min and Max Queries, we'll modify our Segment Tree to store minimum and maximum values instead of sums.

python

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

    # ... (Same as previous implementation, but store min and max instead of sum)

    def merge(self, index):
        self.tree[index] = min(self.tree[2 * index], self.tree[2 * index + 1])
        self.tree[index] = max(self.tree[index], self.tree[2 * index], self.tree[2 * index + 1])

    def query(self, index, ss, se, qs, qe, node):
        if qs <= ss and se <= qe:
            return self.tree[index]
        if ss > qe or se < qs:
            return (float('inf'), float('-inf'))
        mid = (ss + se) // 2
        left_min_max = self.query(2 * index, ss, mid, qs, qe, node)
        right_min_max = self.query(2 * index + 1, mid + 1, se, qs, qe, node)
        return (min(left_min_max[0], right_min_max[0]), max(left_min_max[1], right_min_max[1]))

arr = [1, 3, 5, 7, 9]
seg_tree = SegmentTree(arr, len(arr))
print(seg_tree.query(1, 2, 4))  # Should output (3, 9) (min and max values from index 2 to 4)

Put Your Knowledge to the Test 🎯

That's it for our comprehensive guide on Range Queries (Sum, Min, Max)! By now, you should have a solid understanding of these powerful techniques. Happy coding! 🎉