Difference between revisions of "TADM2E 3.13"

Latest revision as of 20:16, 9 July 2017

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[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] $.

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;
       addS(i, y, 0);
   }
   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);
       }
   }
 }