Thread: sum(S,k1,k2) in O(logn)???

i have a h.w about red black trees.
they ask to find a data structure that support the following algorithems
1. insert in O(logn)
2.delete in O(logn)
3. pair-dif(S,d)-find x1,x2 that x2-x1=d>0
in O(n) time
4. sum(S,k1,k2)- return the sum of all the values between k1 and k2
in O(logn)
i used RB tree to solve 1-3 but i don't know how to solve 4.
every time i think on a solution it evolve summing all the members in which k1<x<k2 and considering the fact that k1<min(S)<max(S)<k2
may happen it mean O(n) time.
i don't have any limitation on space complexity.
thanks for the help

the solution to 1-2 is to use the RB-INSERT RB-DELETE given in the book
in 3 i can create an arrray B[n] and using an alghrithem called INORDER-WALK-TREE sort the keys in the array(O(n) time)
then i can do the classic SUM-2 solution on a sorted array(O(n)) time

Yes i understand the solution in the book. I have to cause in some of the questions in this course i have to "open"
The algorithem and change it so it will have new properties. Meaning i have to understand each and every line in it.

I thought on this solution. The problem is that beacuse of the structure of binary tree even if for example father<k1 his son or his son son
Exp my still be in the range meaning i`ll have to find manually all his decended in the range.

Ensure node values are unique. If you want duplicates, store them as a count for the node with that value.

Maintain a sum for the subtree rooted at each node, inclusive of the node's total value (node.value * node.count). This is easy to maintain and doesn't add to the complexity of additions, deletions, rotations.

Code:

Example: (node.value, node.sum)    // assume all node.count's are 1

                            10,94
              5,21                        15,63
       3,3             7,13        13,13         17,35
                   6,6                                 18,18

Consider how to use the above info to calculate the sum from the smallest value up to a particular value, like from 3 to 6, 3 to 10, 3 to 17. You can use those sums to calculate the sum between any two values.