TADM2E 3.13

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.