1. 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, how the running time meets the requirements, and what the space requirements are.