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

I'm not sure what you mean by the pyramid-shaped configuration. In any case, n queries taking log(n) + n time each is O(n log n). I think you're right that a range tree should work fine.

I mean this thing from the article:

https://briangordon.github.io/images/worstcase.svg

> n queries taking log(n) + n time each is O(n log n)

No, it's O(n^2).

Wow, clearly commenting too late. Of course you're right :)