An array A contains n numbers. Design a data structure to support the following operations:

• add(i,v) - add the value v to the ith number
• partialSum(i) - return the sum of the first i numbers

Each operation should take O(log n) time. The data structure should take at most O(n) space. Explain how your data structure works, how each of the operations are realized, and how the running time and space meets the requirements.