I would like to have an online data structure that supports inserting an interval, and given a query interval $ I_q=[l_q,h_q]$ answer if $ I_q$ is contained at some interval of the data structure, i.e. if $ I_q$ is a super-interval of some interval of the structure (so *the answer of the query is just boolean*, no need to output all such intervals on the structure) at the fastest possible time complexity.

I have searched for such a combination, and found out that probably an Interval Tree would be appropriate for my situation, with $ O(\log n)$ interval insertion and overlapping intervals query (so it’s not exactly my desired query, but I think that it could possibly be turned to it. Also I can avoid the output complexity dependence, since the desired output is boolean and therefore on the first match I would know the answer is true).

Furthermore, here (https://en.wikipedia.org/wiki/Interval_tree) it is stated that:

If the endpoints of intervals are within a small integer range (e.g., in the range [1,…,O(n)]), faster data structures exist with preprocessing time O(n) and query time O(1+m) for reporting m intervals containing a given query point.

Since I also can guarantee that both interval ends are going to be small **integers** (i.e. not floats, but natural integers up to $ \approx 10^6$ ), what would be the best data-structure/algorithmic way (considering time-complexity of the above two operations) to implement those two operations I would like to have?

If the fastest time-complexity would be an Interval Tree, then how can I modify the overlapping-intervals query to support my query in $ O(\log n)$ time, i.e. not $ O(k\cdot\log n)$ where $ k$ is $ I_q$ ‘s range? However, I am quite interested in the above quoted passage, and how I could possibly (with another data structure, maybe?) manage such a fast complexity, so in that case Interval Trees wouldn’t matter.

Note: In my attempt to test such an algorithm and speed on an Interval Tree, I have found out the following library: https://github.com/chaimleib/intervaltree/blob/master/intervaltree/intervaltree.py where a similar query seems to be implemented on the `envelop`

query with a time-complexity of $ O(m+k\cdot\log n)$ , where “$ n$ = size of the tree, $ m$ = number of matches, $ k$ = size of the search range”, which however is not as fast as I would like (especially considering the $ k$ multiplying factor).