Data Structure to calculate which interval a point lies in? [closed]

Question

I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$.

Each of these intervals has a corresponding value $v_i$ corresponding to it.

Now I have another interval $[x,y], a_1 \leq x < y \leq a_{n+1}$. I want to query the $n$ intervals and find the sum of values of the overlapping intervals with it in $O(\log n)$ time.

To make it clearer, I'll give an example.

Suppose the intervals are $[0,2],[2,4],[4,10]$ with values corresponding to $1,3,5$.

For the interval $[0,3]$, the first and second intervals overlap with it so a total value of 1+3=4.

For the interval $[0,5]$, all three overlap with it so a total value of 1+3+5=9.

For the interval $[5,9]$ only the last one overlaps it so the total value is 5.

I know that I can use a segment tree and query the point based on my interval $[a,b]$. However, how would I calculate the sum of all the values of all the intervals in between also in $O(\log n)$?

Answer 1

Since the intervals are non-overlapping, this can be done by building a 1-D summed area table of the interval values. Building the table takes $O(n)$ time; querying the table consists of two $O(\log n)$ binary searches followed by an $O(1)$ subtraction.

---

Note that the above solution specifically only works because the operation we want to perform on the interval values (addition) is invertible. It is also possible to design a more general data structure that has the same asymptotic performance and works on values from any monoid, using a trick similar to the parallel prefix sums algorithm.

For the initial construction, in $O(n)$ time we build a balanced binary tree, where each leaf node is labeled with an interval/value pair from the problem input, and each internal node is labeled with the union of its two child intervals and the sum of its two child values. For your example problem, the binary tree might look like this:

       [0,10]=9
      /        \
[0,2]=1        [2,10]=8
              /        \
         [2,4]=3     [4,10]=5

To query the data structure, you perform the following steps:

1. Use two $O(\log n)$ binary searches in the tree to find the endpoints of the smallest union of input intervals that contains the query interval. (Same as in the first solution.)
2. Sum the values of all of subtrees whose intervals are between these endpoints in the tree. Since we already have cached values for each subtree, only $O(\log n)$ node values need to be summed together.

For your example queries:

• For the interval [0,3], we find the containing interval [0,4], then compute 1 + 3 = 4.
• For the interval [0,5], we find the containing interval [0,10], then compute 9 = 9.
• For the interval [5,9], we find the containing interval [4,10], then compute 5 = 5.