How many range are completely inside a given range

Question

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

c <= a_i & b_i <= 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?

Answer 1

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$".

Answer 2

There are probably existing data structures for this problem, but I am not familiar with them. Instead, I will just create something with the tools I am familiar with.

Assume that the ranges are stored in arrays $A$ and $B$ so that $A[i] = a_i$ and $B[i] = b_i$ and that the ranges are sorted by their starting points. Given a query range $[c, d]$, we can binary search array $A$ to find the interval $A[sp, ep]$ of ranges starting in $[c, d]$.

To solve the counting version of the problem, we store array $B$ as a wavelet tree. We can then report the number of endpoints $b_i \le d$ in interval $B[sp, ep]$ in $O(\log n)$ time.

If we also want to list the ranges contained in $[c, d]$, we can do that in $O(\log n)$ time per range by using the wavelet tree. We can get the time down to $O(1)$ / range with a range minimum query data structure over array $B$. We find the smallest value $b_i$ in $B[sp, ep]$, check whether $b_i \le d$, and then continue recursively to $B[sp, i-1]$ and $B[i+1, ep]$.

The solution based on wavelet trees assumes that the endpoints are integers. If they are not, we can simply map them into integers by binary searching the sorted array of endpoints.

Example. We have seven ranges: $[2, 6]$, $[3, 4]$, $[3, 5]$, $[4, 8]$, $[5, 6]$, $[6, 7]$, and $[8, 9]$. The arrays are therefore $A = (2, 3, 3, 4, 5, 6, 8)$ and $B = (6, 4, 5, 8, 6, 7, 9)$.

Assume that the query range is $[c, d] = [3, 6]$, which contains three ranges: $[3, 4]$, $[3, 5]$, and $[5, 6]$. By binary searching array $A$, we find that the starting points of the ranges starting in $[3, 6]$ are in the interval $A[2, 6] = (3, 3, 4, 5, 6)$. The corresponding interval of endpoints is $B[2, 6] = (4, 5, 8, 6, 7)$.

The root of the wavelet tree partitions array $B$ into "small" and "large" values and stores the partitioning as a bitvector. Its left and right subtrees are wavelet trees for the subsequences of "small" and "large" values, respectively. If we consider values $\le 5$ "small", the bitvector at the root is $V = (1, 0, 0, 1, 1, 1, 1)$, and the "small" and "large" subsequences are $S = (4, 5)$ and $L = (6, 8, 6, 7, 9)$, respectively.

Bitvector $V$ supports $rank(i, b)$ ("how many $b$s are there in prefix $V[1, i]$") queries in constant time.

We want to count the number of values $\le 6$ in $B[2, 6]$. As $6$ is a "large" value, we first determine the number of "small" values in the interval as

$rank(6, 0) - rank(2 - 1, 0) = 2 - 0 = 2$.

Then we determine the number of "large" values $\le 6$ in $B[2, 6]$ recursively by going into the right subtree. Interval $B[2, 6]$ in the root corresponds to interval

$L[rank(2 - 1, 1) + 1, rank(6, 1)] = L[2, 4] = (8, 6, 7)$

in the right subtree, and the number of values $\le 6$ in $L[2, 4]$ is also the number of "large" values $\le 6$ in $B[2, 6]$. The recursion eventually stops, reporting one such value. Hence the number of values $\le 6$ in $B[2, 6]$ is $2 + 1 = 3$.

Answer 3

You could simply use a multidimensional index, such as an R-Tree or R*tree, which can be used to perform inclusion queries for rectangles or cubes. In your case, you would simply use a 1-dimensional version of these trees.