Data structure for querying if a given interval is enclosed by a set of other intervals

Have a balanced binary tree of some sort of endpoints along with whether they are open or closed.

To insert [a, b] your logic will look like this:

let x be the last event before a (if any)
let y be the next event after b (if any)
delete all events between x and y (if any)
if x doesn't exist or is a close:
    insert (a, open) into the tree
if y doesn't exist or is an open:
    insert (b, close) into the tree

Now it may be that inserting an interval will be very expensive (because you are dealing with a long range). But the amortized cost of every interval is O(log(n)) because that's the cost to do the lookup, the cost to insert if you need to, and the cost to delete later.

The cost of testing enclosure is O(log(n)). Find the last event before or equal to the start of the interval. If it is an open, and the next event is a close at or after the end, then it is enclosed. Else not.