Difference between revisions of "TADM2E 3.13"
| Line 1: | Line 1: | ||
| − | + | 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]. | ||
Revision as of 02:34, 9 July 2017
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].
