Let A[1..n] be an array of real numbers. Design a data structure to perform any sequence of the following operations: Add_At_Index(y, index) - Add the value y to the number at index. Partial_Sum(index) - Return the sum of the first index numbers, i.e. There are no insertions or deletions; the only change is to the values of the numbers. You are allowed to define your own subroutines. Each of the above operations should take O(log(n)) steps. Initialization of the data structure can take O(n). You may use one additional array of size n as a workspace.

Rubric:

Outlined Process

includes process: 1. Initial approach, notes, partial solutions 2. Explanation 3. Final solution with references/search terms 4. Reflection deduct if missing part(s) of this process or if process is not clearly labeled

Correct Solution with Justification

must include a brief justification of runtime somewhere deduct for each function if missing or largely incorrect (smaller deductions if at least the approach is mostly correct) deduct if Add_At_Index doesnt update the Partial Sum tree (results in O(n) runtime for at least 1 function)