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 temp closestToLow <- findClosest(low) if(low=closestToLow) 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.