Difference between revisions of "TADM2E 3.13"

From Algorithm Wiki
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
Note: the following solution does not meet the requirements of the problem, having a binary tree of n leaves and thus 2n - 1 nodes. The requirements are to use no more than an n-size array:
+
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:
  
Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.
+
  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]
 +
  }
  
Querying a partial-sum goes like this: Descend the tree towards the query (leaf) node, but whenever you descend right, add the subtree-sum on the left, since we know for sure those elements are in the sum.
+
Then, <math>Add(i, y)</math> will add <math>y</math> to the value of each tree node, starting from the root, as well as the leaves defined in <math>A</math>. Likewise, <math>Partial-sum(i)</math> 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 <math>S[1..m] (m < n)</math> be such an array of BNode objects.
 +
 
 +
<math>S[0]</math> is the root, with value equal to the sum of <math>A[0..n]</math>.
 +
<math>S[1]</math> is root's left child, with value equal to the sum <math>A[0..n/2]</math>.
 +
<math>S[2]</math> is root's right child, with value equal to the sum of <math>A[n/2+1..n]</math>.
 +
 
 +
In general, <math>S[i]</math> will have value equal to the sum of <math>S[i]</math>'s children at <math>S[2*i+1]</math> and <math>S[2*i +2]</math>. 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);
 +
        }
 +
    }
 +
  }

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);
       }
   }
 }