Difference between revisions of "TADM2E 3.13"

From Algorithm Wiki
Jump to: navigation, search
(Recovering 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 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.

Revision as of 18:05, 8 July 2017

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.

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.