Interval Trees and Overlap Queries

Suppose you've stored thousands of intervals — trading halts, earnings blackout windows, market hours across venues — each with a start and end time, and you need to repeatedly ask "which of these intervals overlap this particular time range?" Checking every stored interval against the query one by one is $O(n)$ per query, which becomes a real bottleneck once you're running that check millions of times against a large dataset. An interval tree answers the same question in $O(\log n + k)$ time, where $k$ is the number of overlapping intervals actually returned.

The structure is built as a balanced binary search tree keyed on each interval's start point, where every node additionally stores the maximum end point across its entire subtree. That extra "max end" annotation is what makes the speedup possible: when searching, the tree can immediately discard whole subtrees whose maximum end point falls before the query's start, without inspecting a single interval inside them, because none of them could possibly overlap.

A market-data pipeline checking whether a given trade timestamp falls inside any known trading-halt window across thousands of symbols and days is a direct fit: build one interval tree per symbol at startup, then each trade lookup is a fast tree query instead of a linear scan through every recorded halt.