Are you sure that it's n log n? I think that the pyramid shaped configuration defeats this strategy by forcing the interval tree to report something on the orde

Are you sure that it's n log n? I think that the pyramid shaped configuration defeats this strategy by forcing the interval tree to report something on the order of n intervals with every query. So there are n queries on the interval tree, and each query takes log(n) + n time. Also, something interesting to note that I was thinking about yesterday is that you don't actually need to use an interval tree for this. You can use a range tree instead, which is simpler (to my mind). You only need an interval tree to do a certain kind of query which we never need to do: https://briangordon.github.io/images/range-interval.png https://briangordon.github.io/images/range-interval.png