Data structure for interval subset queries

Question

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$?

Answer 1

Summary

Yes, a persistent segment tree for the sums of ranges over an array of counters can do it.

Please run the example program in Java here.

Intuition

There are at most $|S|$ ending values for all intervals in $|S|$. We can build a persistent segment tree: we process intervals in order of increasing starting point, incrementing a counter corresponding to that interval's ending point, and use a persistent segment tree to enable us to compute suffix sums on the array of counters at any point in time. For each query, choose the appropriate version of the segment tree to get the desired count.

A specialized persistent segment tree

Given an array $S$ of intervals, let us build a persistent segment tree with $|S| + 1$ versions. In other words, we will build $|S|+1$ segment trees. An array of that length will store the root nodes of those trees.

All arrays are 0-indexed.

0. Since only comparison matters while the actual magnitude of values is not, we can replace each endpoint of all intervals in $S$ by its standard competition rank among all endpoints of all intervals in $S$. This is the usual compression/ranking step on problems about comparisons.
   Let $B$ be the array of the starting points of all intervals in $S$ and $M$ be the unranking mapping, which maps each element of $B$ to the original starting point of a given interval.

1. Create an array $E$ of $|S|$ zeros. This array is only used to help explain the data structure and the algorithm. It does not show up explicitly in the data structure nor the algorithm.

2. Initialize an array $J$ of $|S|+1$ nodes. $J[i]$ will be the root node of the segment tree of version $i$.

3. Created the segment tree of version 0, all nodes of which have value 0. This corresponds to the initial state of $E$.

4. Sort $S$ by the starting point of each interval, breaking ties arbitrarily.

5. One by one process the sorted $S$. Suppose the current interval is the $i$-th interval, $[l, r]$. Construct the segment tree of version $i+1$ by updating the segment tree of version $i$ as if we have added 1 to $E[r]$. Check this article or this article to get an idea how this updating is done. Read my program in Java for the exact details.

The data structure we wanted is the combination of the array of $|S|+1$ segment trees, a.k.a a persistent segment tree, the array $B$ and the unranking mapping $M$.

Handle the queries

Suppose $q=[l_q, r_q]$ is a query interval. Here is how we find the number of all intervals in $S$ that contain $q$.

1. Find the index of the last interval in sorted $S$ whose starting point, when mapped to its original starting point before ranking (i.e., unranking by $M$), is not bigger than $l_q$, using binary search. If there is no such index, return 0 and stop.
2. Let the index found at step 1 be $i$. Return $J[i+1].\text{sum}(r_q, |S|)$, which is the sum of elements with indexes no less than $r_q$ in array $E$ at the time right after the $i$-th interval had been processed during step 5 of the construction above, and, hence, which is the number of all intervals in $S$ that contain $[s_q, e_q]$.

Time Complexity analysis

The standard construction of a persistent segment tree of $v$ versions for the range sums of an array of length $m$ runs with $O(m + v\log m)$ time-complexity. Here we have $v=|S|+1$ and $m=|S|$. The ranking of all endpoints takes $O(|S|\log |S|)$ time. Including other immaterial running cost, we find the construction of the data structure takes $O(|S|+ (|S|+1)\log |S|)=O(|S|\log|S|)$ time.

For a given query interval, find the right version of the segment tree takes $O(\log |S|)$ time. It takes another $O(\log |S|)$ time to get the number of containing intervals as the range sum. So, each query takes $O(\log |S|)$ time.

Space Complexity

It requires $O(|S|\log |S|)$ space to store the persistent segment tree.

Answer 2

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.