TADM2E 3.13

Let A[1..n] be the same as the problem definition.

Before outlining the solution, consider that a binary tree can satisfy the O(logn) requirement for both the Add(i, y) and Partial-sum(i) functions. In so doing, we initialize the binary tree with all non-leaf nodes equal to the sum of all values of nodes of their children, where each node has the following structure:

class BNode {

 int min;  // minimum index of A[] contained by a child
 int max; // maximum index of A[] contained by a child
 int value; // sum of A[min..max]

}

Then, Add(i, y) will add y's value to the value of each tree node, starting from the root, until reaching the ith leaf. Likewise, Partial-sum(i) is implemented recursively (not implemented here) using the structure of the tree to ensure no more than 2 nodes' values are added, which cleanly partition A[0..x] and A[x +1..i], returning the sum of A[0..i].

Unfortunately, the problem allows only an n-size array as a workspace. However, consider that a binary tree with n leaves will have no more than n - 1 non-leaf nodes. Using the heapsort's method of organizing the non-leaf nodes in an array (see heapsort), we can satisfy this requirement:

Let S[1..m] (m < n) be such an array of BNode objects.

S[0] is the root, with value equal to the sum of A[0..n]. S[1] is root's left child, with value equal to the sum A[0..n/2] S[2] is root's right child, with value equal to the sum of A[n/2+1..n]

and in general, S[i] will have value equal to the sum of S[i]'s children at S[2*i+1] and S[2*i +2]. There will never be more than one element of the array with min == max, which will have value equal to A[min].