Given intervals, answer queries of the form "which intervals contain point ?" or "which intervals overlap with ?" Brute force: for each query, scan all intervals.
Time: . For intervals and queries, that's operations. Too slow. You need a data structure that:
Preprocesses intervals in
Answers overlap queries in where is the result size Interval trees achieve exactly this. Here's the trick: organize intervals by their midpoints to enable binary search.