0
$\begingroup$

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

$\endgroup$

closed as off-topic by D.W., Kaveh, David Eppstein, Mohammad Al-Turkistany, Jeffε Jul 22 '17 at 6:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – D.W., Kaveh, David Eppstein, Mohammad Al-Turkistany, Jeffε
If this question can be reworded to fit the rules in the help center, please edit the question.

5
$\begingroup$

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.
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.