Segment Tree for Min-Max Range Query

The Query Algorithm: Divide, Conquer, and Combine

Just like building the tree, querying it is a recursive process. The goal is to find the minimum and maximum values in a specific query range, let's say [l, r]. We start at the root of the tree and traverse downwards. At each node, which represents its own range [tl, tr], we face one of three scenarios:

1. No Overlap: The node's range is completely outside our query range [l, r]. This branch of the tree is irrelevant to our query, so we can ignore it.
2. Total Overlap: The node's range is completely inside our query range [l, r]. Since this node already has the pre-computed min and max for its entire range, we can just return its value and stop traversing down this path. This is the key to the algorithm's efficiency.
3. Partial Overlap: The node's range partially intersects with our query range. We can't use this node's value directly, nor can we ignore it. We must continue our search by making two recursive calls: one to the left child and one to the right child, and then combine their results.

To see a great visual explanation of these three rules, the following video segment is invaluable.

The reason this algorithm is so fast (O(log n)) is that any query range [l, r] can be perfectly covered by at most 2 * log(n) nodes in the tree. At each level of the tree, we only ever explore at most two "partial overlap" nodes—the ones on the edges of our query range. Any nodes in between will be fully contained.

Implementing the Query in C++

Let's add the query functionality to our MinMaxTree class. We'll follow a standard pattern: a public-facing method that calls a private recursive helper function.

First, how do we handle the "No Overlap" case? We need to return a value that, when combined with other results, doesn't alter them. This is the identity element for our combine operation. For a min/max query, this would be:

• min_val: Positive infinity
• max_val: Negative infinity

Let's update our MinMaxNode and combine function from the last lesson to handle this.

#include <limits> // Required for std::numeric_limits

// Inside the MinMaxTree class
private:
    struct MinMaxNode {
        T min_val = std::numeric_limits<T>::max(); // Identity for min
        T max_val = std::numeric_limits<T>::lowest(); // Identity for max
    };

    MinMaxNode combine(const MinMaxNode& left, const MinMaxNode& right) {
        return {
            std::min(left.min_val, right.min_val),
            std::max(left.max_val, right.max_val)
        };
    }

Note: lowest() is used for floating-point types to get the most negative finite value, which is safer than -infinity in some contexts. For integers, it's equivalent to min().

Now we can write the recursive query function. It needs to know the index of the current node (node_idx), the range that node covers (range_start, range_end), and the range we are querying for (query_l, query_r).

// Private recursive query function
MinMaxNode query(size_t node_idx, size_t range_start, size_t range_end, size_t query_l, size_t query_r) {
    // 1. No Overlap: The node's range is completely outside the query range.
    // Return the identity node.
    if (range_start > query_r || range_end < query_l) {
        return MinMaxNode{}; // Returns the identity {max, lowest}
    }

    // 2. Total Overlap: The node's range is completely inside the query range.
    // Return the pre-computed value for this node.
    if (query_l <= range_start && range_end <= query_r) {
        return m_tree[node_idx];
    }

    // 3. Partial Overlap: Recurse on children and combine results.
    size_t mid = range_start + (range_end - range_start) / 2;
    size_t left_child_idx = 2 * node_idx + 1;
    size_t right_child_idx = 2 * node_idx + 2;

    MinMaxNode left_result = query(left_child_idx, range_start, mid, query_l, query_r);
    MinMaxNode right_result = query(right_child_idx, mid + 1, range_end, query_l, query_r);

    return combine(left_result, right_result);
}

Finally, the public method provides a clean interface. It performs some basic validation and starts the recursion from the root node (index 0), which covers the entire original data range (0 to m_num_leaves - 1).

// Public query function
public:
    MinMaxNode getMinMaxInRange(size_t l, size_t r) {
        if (m_tree.empty() || l > r) {
            return MinMaxNode{};
        }
        return query(0, 0, m_num_leaves - 1, l, r);
    }

The resource cp-algorithms.com provides an excellent, compact implementation for a sum query. The logic is identical to our min-max query, just with a different combine operation. Notice its clever way of splitting the query range in the recursive calls. While our implementation above works perfectly, the cp-algorithms version is a robust alternative worth studying.

To solidify this, let's watch the final segment of Tushar Roy's video, where he does a detailed code walkthrough of the query function, tracing the recursive calls and return values just like we did in the exercise.

Conclusion

Excellent work. We have now completed the MinMaxTree data structure. It can be constructed from an array of data points and can efficiently query the minimum and maximum values over any arbitrary sub-range.

Key Takeaways:

• The query algorithm works by recursively traversing the tree and applying one of three rules at each node: No Overlap, Total Overlap, or Partial Overlap.
• The O(log n) complexity is achieved because "Total Overlap" cases prune entire subtrees from the search, and any query range can be covered by a logarithmic number of such nodes.
• The implementation uses a private recursive helper that handles the tree traversal, while a public method provides a simple, clean API.
• An identity element ({min: infinity, max: -infinity}) is crucial for handling "No Overlap" cases correctly during the combine step.

Our data structure is now ready for use in the LOD plotter.

What's Next?

We have a powerful tool, but how do we use it for visualization? A user doesn't specify data indices l and r; they interact with the plot by zooming and panning.

In the next lesson, we will bridge the gap between user interaction and our data structure. We will implement the logic to calculate the visible data range based on the current zoom and pan state. This will tell us which range of indices we need to pass to our getMinMaxInRange function to draw the correct view of the data.