How many range are completely inside a given range

I have a list of ranges ai , bi. And I have many queries in the form of a range c, d, which asks how many ranges ( ai, bi‌ ) are completely inside c, d.

c i & bi <= d

There are so many of these queries. So I want to know if there is an algorithm that answer each query in a time complexity that is better than O(n).

My first attempt was to use two sorted list. One with respect to the end point of ranges and the other with respect to the start point of ranges. This way I can find how many ranges start after c, and how many ranges end before d. But I couldn't find a way to calculate their union. So this attempt was unsuccessful.

My second idea was to use Interval Tree. Interval Tree can help you find whether any ranges overlap with a certain range. I couldn't come up with a modification so that it gives me what I want instead of just overlaps. My best attempt had time complexity of O(n) for each query. For example if the ranges were are all equal my query would take O(n) but this wasn't the only example and there were a lot of other cases that the result of each query would take O(n).

So now I am wondering whether there is a data structure or an algorithm that helps me do these queries in sub-linear time?

I've given an answer to the question with the similar idea here. I'll recall the most important parts of the data structure in this answer. It looks similar to the solution with wavelet trees by Jouni but, I think, is easier to code (arguable).

Here is the data structure which is sometimes called Merge Sort Tree. It is basically a segment tree where each node stores a sorted subarray. This structure requires $O(n \log n)$ memory (because there are $\log n$ layers and each of them requires storing $n$ numbers). It is built in $O(n \log n)$ as well: you just go bottom-up and for each inner vertex merge sorted lists of its children.

Here is an example. Say 1 5 2 6 8 4 7 1 be an original array.

|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|

This structure can answer queries of form "how many numbers $\leq x$ are there in range $[l, r]$" in $O(\log^2 n)$ time: just make a reqular query to a segment tree (traversing $O(\log n)$ nodes) and make a binary search to know how many numbers $\leq x$ are there in that node (additional $O(\log n)$ from here).

This can be speed up to $O(\log n)$ using Fractional Cascading technique, which basically allows you to do the binary search not in each node but only in the root. However it is complex enough to be described in the post.

The original problem is reduced to this one exactly the way Jouni explained: having your segments sorted by left endpoint, you create the array of left endpoints $A$ and a Merge Sort Tree of right endpoints $B$. Use the binary search on $A$ to find the range, $[l, r]$, of indexes of left endpoints lying in $[c, d]$ and make a query "how many numbers $\leq d$ are there in range $[l, r]$ in array $B$".

StackExchange Computer Science Q#64137, answer score: 8