Find all intervals that are contained in a query interval
You were too quick to reject interval trees and segment trees.  You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward recursive procedure:

Any node $v$ of a segment tree has a corresponding interval $\text{Int}(v)$.  Do a recursive search of the tree, except that you only visit nodes $v$ such that $\text{Int}(v)$ overlaps $q$.  Each such node stores a list of intervals from $S$.  For each such node, if $\text{Int}(v)$ is contained in $q$, check all of the intervals stored with $v$ is contained in $q$.

That's all you need to do.  Just because a data structure is designed to support one kind of operation doesn't mean it's unable to support other operations, too.

That said, one challenge with segment trees is that it's not clear how to update them dynamically (to add new intervals).



I think similar ideas can also be applied to interval trees, too.  The root of an interval tree has a value $x$.  Now do a case analysis:


If $x$ is to the left of $q$ (i.e., $x &lt; \ell_q$), then you only need to look at intervals that are completely to the right of $x$, so you just recurse to the right child of the root.
If $x$ is to the right of $q$ (i.e., $x &gt; u_q$), then you only need to look at intervals that are completely to the left of $x$, so you just recurse to the left child of the root.
If $x \in q$ (i.e., $\ell_q \le x \le u_q$), then you recurse to the left child and output all matches found there; recurse to the right child and output all matches found there; and finally, find all intervals that contain $x$ and are contained in $q$.  The latter can be done by scanning the list of intervals associated with the root (which is a list of intervals that contain $x$), to see which meet your condition.




I suspect there might be other approaches as well.  For instance, you could build a $k$-d tree, with $k=2$ dimensions, where the interval $[\ell,u]$ is represented as the point $(\ell,u)$.  Then given a query interval $q=[\ell_q,u_q]$, you want to do a range search to find all points $(x,y)$ such that $x \ge \ell_q$ and $y \le u_q$.  That should be a straightforward recursive search in a $k$-d tree.  Or, you could build a quadtree.