Min-Max Tree Data Structure for Aggregated Data

The Core Problem: Fast Range Queries

The problem from our last lesson boils down to this: for any given horizontal pixel range on our plot, we need to find the minimum and maximum data values within that range instantly. If we can do that, we can draw a single vertical line representing potentially thousands of data points, as suggested by the KDAB article "A Speed-Up for Charting on Embedded".

Doing this naively by scanning the array for each query is too slow. We need a more intelligent data structure. This is a classic problem in competitive programming and systems design, and the solution is a Segment Tree. For our specific use case, we'll be implementing a variant of it that we'll call a Min-Max Tree.

To understand why a specialized tree is so effective, let's watch a short video that compares the performance of different approaches.

An O(log n) query time is exactly what we need. It means that even if our dataset grows from one million to one billion points, the time it takes to query a range will only increase by a tiny, constant amount.

The Conceptual Structure: A Tree of Aggregates

A min-max tree is a binary tree built on top of our original data array. Here’s how it works:

• Leaf Nodes: Each leaf node in the tree corresponds to a single data point from the input array.
• Internal Nodes: Each internal (or parent) node stores the aggregated minimum and maximum values of the entire range covered by its children.
• Root Node: The root of the tree stores the global minimum and maximum of the entire dataset.

This hierarchical structure allows us to "zoom out" from individual data points to larger and larger summary ranges.

Let's see this structure being built.

Designing the Node Data Structure

The first step in designing our tree in C++ is to define the data that each node will hold. Based on our goal, every node must store the minimum and maximum value for the range it represents. A simple struct is perfect for this.

template <typename T>
struct MinMaxNode {
    T min_val;
    T max_val;
};

This is very similar to the node struct in the GeeksForGeeks article "Min-Max Range Queries in Array". When we build the tree, each MinMaxNode will be initialized. For leaf nodes, min_val and max_val will both be the value of the single data point it represents. For an internal node, its values will be computed from its children:

• parent.min_val = std::min(left_child.min_val, right_child.min_val);
• parent.max_val = std::max(left_child.max_val, right_child.max_val);

This simple, recursive definition is the foundation of the build process we will implement in the next lesson.

Designing the Tree Storage: An Array for Performance

While we call it a "tree," implementing it with pointers (Node* left_child;) would be a performance mistake. As we learned in the last lesson, pointer chasing leads to scattered memory access and frequent cache misses. This is contrary to the Data-Oriented Design philosophy of our project.

The performant solution is to store the entire tree in a single, contiguous block of memory: a std::vector or a raw array. We can map the tree structure to array indices using a standard formula derived from binary heaps:

For a node at index i:

• Its left child is at index 2 * i + 1.
• Its right child is at index 2 * i + 2.
• Its parent is at index (i - 1) / 2 (using integer division).

This layout is extremely cache-friendly. When you access a parent node, its children are likely already in the same cache line or will be brought in by the prefetcher.

The following video segment explains this array representation and how to calculate the required size of the array.

Putting It All Together: A C++ Class Design

We can now sketch out a preliminary design for our MinMaxTree class in C++. This API is inspired by the one proposed in the excellent KDAB article, which is highly relevant to our charting goal.

#include <vector>
#include <limits>
#include <algorithm> // for std::min/max

template <typename T>
class MinMaxTree {
public:
    // Constructor: Takes the original data and builds the tree
    MinMaxTree(const std::vector<T>& data) {
        // We will implement the build logic in the next lesson
    }

    // Public query function
    MinMaxNode<T> getMinMaxInRange(size_t rangeBegin, size_t rangeEnd) const {
        // We will implement the query logic in a future lesson
    }

private:
    // The struct for our nodes, as defined before
    struct MinMaxNode {
        T min_val = std::numeric_limits<T>::max();
        T max_val = std::numeric_limits<T>::lowest(); // Note: NOT ::min()!
    };

    std::vector<MinMaxNode> m_tree;
    size_t m_num_leaves; // The number of elements in the original data array
    
    // Private recursive helper functions for building and querying
    // void buildRecursive(...);
    // MinMaxNode queryRecursive(...) const;
};

This class encapsulates the design principles we've discussed:

1. It's a template, so it can work with float, double, int, etc.
2. It stores the tree in a single std::vector (m_tree) for performance.
3. It exposes a clean public API for querying, hiding the complex recursive logic.
4. The MinMaxNode is a private implementation detail. Notice the initialization values, which ensure that any real data point will correctly replace the initial defaults. The KDAB article (LINK, section 2) has a great warning about std::numeric_limits<T>::min(), which is a common pitfall!

A Data-Oriented Refinement: Buckets

The KDAB article also suggests a powerful optimization that fits perfectly with our goals. Instead of each leaf node representing a single data point, it can represent a small, fixed-size array of points, often called a "bucket".

The design implication is this:

• The tree becomes much shorter and wider.
• When a query range falls entirely within a single leaf bucket, we do a fast linear scan on that small bucket.
• This is extremely cache-efficient, as the entire bucket (e.g., 64-128 elements) will likely fit in a single CPU cache line.

For our design, this means we can choose to have the leaves of our MinMaxTree point to ranges in the original data array, rather than storing single values. This is an advanced design choice we will consider during implementation to squeeze out maximum performance.

Conclusion

We have now designed the data structure that will form the backbone of our efficient LOD plotter. We've moved from a high-level concept to a concrete C++ class design, making specific choices to prioritize performance and align with data-oriented principles.

Key Takeaways:

• A Min-Max Tree (a type of Segment Tree) is a binary tree that stores pre-aggregated minimum and maximum values for ranges of an underlying data array.
• The node structure is simple: it just needs to hold a min_val and a max_val.
• For performance, the tree should be stored in a contiguous array or vector, not with pointers, using heap-style indexing (2*i+1, 2*i+2) to navigate.
• The design can be further optimized by using buckets at the leaf nodes, which improves cache locality for small range scans.

What's Next?

With a solid design in place, the next logical step is to bring it to life. In the next lesson, we will focus on the learning outcome: Implement a bottom-up algorithm to build the min-max tree from an array of data points. We will write the C++ code for the build logic we sketched out today, turning our data structure design into a functional component.