Interval Trees and SortedList: When O(log n) Stabbing Queries Matter

Concepts: pyIntervalTree, pySortedList, pyStabbingQuery

Sort-merge covers the batch case perfectly: you have all intervals upfront, sort once, scan once. But what happens when intervals arrive dynamically — one at a time — and you need to answer 'which intervals contain point P?' after each insertion? Sorting the entire list and scanning is O(n) per query. An interval tree does it in O(log n + k) where k is the number of matching intervals. This is the data structure that makes range queries on dynamic datasets practical at scale. What an Interval Tree Does An interval tree stores intervals such that a stabbing query — 'give me all intervals that contain point x' — runs in O(log n + k) time. The classic implementation augments a BST where each node stores an interval and the maximum end value in its subtree. To find intervals containing x: if x