The Overlap Problem

Given $n$ intervals, answer $q$ queries of the form "which intervals contain point $x$?" or "which intervals overlap with $[l, r]$?" Brute force: for each query, scan all $n$ intervals.

Time: $O(nq)$. For $n = 10^5$ intervals and $q = 10^5$ queries, that's $10^{10}$ operations. Too slow. You need a data structure that:

$1.$ Preprocesses intervals in $O(n \log n)$

$2.$ Answers overlap queries in $O(\log n + k)$ where $k$ is the result size

Interval trees achieve exactly this. Here's the trick: organize intervals by their midpoints to enable binary search.