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 {
BNode left, right;
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$ to the value of each tree node, starting from the root, as well as the leaves defined in $A$. Likewise, $Partial-sum(i)$ is implemented recursively using the structure of the tree to ensure a clean partition of sections of A.

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$ is the root, with value equal to the sum of $A[0..n]$. $S$ is root's left child, with value equal to the sum $A[0..n/2]$. $S$ is root's right child, with value equal to the sum of $A[n/2+1..n]$.

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]$. See solution in Java below.

 public class SumKeeper {
private float[] A;
private BNode[] S;
private int sMax;
class BNode {
BNode(int min, int max, float value) {
this.min = min;
this.max = max;
this.value = value;
}
int min;
int max;
float value;
}
public SumKeeper(float[] A) {
this.A = A;
int ln2 = (int)Math.ceil(Math.log(A.length) / Math.log(2));
this.S = new BNode[(0x1 << ln2) - 1];
initS(0, A.length - 1, 0);
}
private void initS(int min, int max, int sNode) {
if(sNode > sMax) sMax = sNode;
if(min >= max)
S[sNode] = new BNode(min, max, A[min]);
else if (min == max - 1)
S[sNode] = new BNode(min, max, A[min] + A[max]);
else {
int mid = min + (max - min) / 2;
initS(min, mid, 2 * sNode + 1);
initS(mid + 1, max, 2 * sNode + 2);
float sum = S[2 * sNode + 1].value + S[2 * sNode + 2].value;
S[sNode] = new BNode(min, max, sum);
}
}
public void add(int i, float y) {
if(i - 1 > A.length) throw new IndexOutOfBoundsException();
A[i] += y;
}
private void addS(int i, float y, int sNode) {
if(sNode > sMax) return;
S[sNode].value += y;
int mid = S[sNode].min + (S[sNode].max - S[sNode].min) / 2;
if(mid >= i) {
addS(i, y, 2 * sNode + 1);
} else {
addS(i, y, 2 * sNode + 2);
}
}
public float partialSum(int i) {
return partialSum(i, 0);
}
private float partialSum(int i, int sNode) {
if(sNode > sMax) return A[i];
int mid = S[sNode].min + (S[sNode].max - S[sNode].min) / 2;
if(S[sNode].max == i) {
return S[sNode].value;
} else if(mid >= i) {
return partialSum(i, 2 * sNode + 1);
} else {
return S[2 * sNode + 1].value + partialSum(i, 2 * sNode + 2);
}
}
}