TADM2E 3.13 - Revision history

Brandon.arnold at 20:16, 9 July 2017

2017-07-09T20:16:00Z

Brandon.arnold at 19:53, 9 July 2017

2017-07-09T19:53:43Z

Brandon.arnold at 02:34, 9 July 2017

2017-07-09T02:34:49Z

Brandon.arnold at 18:15, 8 July 2017

2017-07-08T18:15:52Z

Brandon.arnold at 18:05, 8 July 2017

2017-07-08T18:05:21Z

Algowikiadmin: Recovering wiki

2014-09-11T18:13:24Z

Recovering wiki

New page

Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.

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.

@@ Line 2: / Line 2: @@
    class BNode {
      int min;   // minimum index of A[] contained by a child
      int max;   // maximum index of A[] contained by a child

@@ Line 1: / Line 1: @@
 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 {
+  class BNode {
-  int min;  // minimum index of A[] contained by a child
+    int min;   // minimum index of A[] contained by a child
-  int max; // maximum index of A[] contained by a child
+    int max;   // maximum index of A[] contained by a child
-  int value; // sum of A[min..max]
+    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].
+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 S[1..m] (m < n) be such an array of BNode objects.
+Let <math>S[1..m] (m < n)</math> be such an array of BNode objects.
-S[0] is the root, with value equal to the sum of A[0..n].
+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.
-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].
+  public class SumKeeper {

@@ 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 O(n) nodes. The requirements are to use no more than an n-size array:
+Let A[1..n] be the same as the problem definition.
-Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.
+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:
-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.
+class BNode {

@@ 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:
+Note: the following solution does not meet the requirements of the problem, having a binary tree of n leaves and thus O(n) nodes. The requirements are to use no more than an n-size array:
 Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.
 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.

← Older revision		Revision as of 18:05, 8 July 2017
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:
		+
	Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.		Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.

	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.		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.