Difference between revisions of "TADM2E 3.13"
From Algorithm Wiki
| 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 | + | 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. | 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. | ||
Revision as of 18:15, 8 July 2017
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.
