Suppose you are given n (key,value) pairs. Design a data structure to support the following operations:

• add(k,v) - add the value v to the element with key k
• partialSum(k) - return the sum of all of the elements whose key is less than k
• insert(k,v) - insert a new value with key k and value v
• remove(k) - remove the item with key k

The worst case running time should be O(n log n) for any series of n operations. Explain how your data structure works, how each of the operations are realized, and how the running time meets the requirements. What are the space requirements?