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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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