Question:

Given a double[ ] A containing N real numbers as input, the partial sums problem specifies the following API describing the basic operations that we need.

add(int i, double y): Add the value y to the ith number.

partialSum(int i): Return the sum of the first i numbers, A[0] through A[i - 1].

There are no insertions or deletions; the only change is to the values of the numbers.

We may introduce one additional array of size N.

Assume for simplicity that N is a power of 2.

It's not allowed to use the segment tree.

Tip: We're allowed to have whatever Big-O time it takes to set up/construct the data structure. It's just the add and partial sum methods that need to be in O(log N).

For the following condition, give a specific English description of a partial sums algorithm that meets the requirements.

1. Runtime for add is in O(log N) while partialSum is in O(log N).