Suggest a data structure to perform a query $sumRange(low,high)$ which will return the sum of the elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time.

I found the original problem here (although it's for counting) but it runs in $\Theta(n)$ time. However, I think with additional data structures and/or improvements this can be done in $\Theta(\log n)$.

I think we need a balanced binary search tree, for example, red-black tree.

Then I thought of the following algorithm:

sumRange(low, high) 
sum <- 0
closestToLow <- findClosest(low)

    sum += closestToLow.key

temp <- successor(closestToLow)
sum += temp.key

It will only find the low point and its successor. I guess we need a similar piece of code to find the high point. Not sure how to traverse in between though.


Prefix sums or a 1-D summed area table suffice to answer those queries in $O(1)$ time. (Alternatively, you can augment a balanced binary search tree -- I will let you discover how.)

  • $\begingroup$ Yes I also though of augmenting the tree with sum field. So intuitively I think we can get the sum of the high bound - sum of low bound but we may take too much this way. So for example all elements to the left of low should be discounted $\endgroup$ – Yos Jul 16 '17 at 18:42

Your Answer

