Data structure for interval subset queries I have a set $S$ of intervals.  I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ that contain $q$, i.e., count the number of intervals $s \in S$ such that $q \subseteq s$.
(This is like a stabbing query, but now the query is an interval, not a single point.)
Is there an efficient data structure for this?  Ideally, one that can be constructed in $O(n \log n)$ time and where each query can be answered in $O(\log n)$ time, where $n$ denotes the number of intervals in $S$?
Let $F(I) = |\{s \in S : s \subseteq I\}|$ where $I$ is an interval.
If $[a, b]$ is our query interval, we can make the following partition where $R$ is our desired result:
$$R =n -F((-\infty, b)) - F((a, \infty)) + F((a, b))$$
The first two queries can be answered simply using a sorted data structure of respectively endpoints and startpoints.
The last query is the dual of this problem, which has an answer here on this site.