Let $a_{1} , ... , a_{m} $ be real numbers $\geq 1$, where $m$ is at least 1. I am supposed to store them in an augmented AVL structure with the following operations:

-PartialSum (i): Return the $i_{th}$ partial sum.

-Change (i, y): Change the $a_{i}$ element for y.

I need this structure to retain the AVL properties and both of these functions to be in $O(logn)$. The problem is that my approach doesn't let me have that asymptotic bound on CHANGE.

My approach goes like this: Let i be the key, and also store the relative $i_{th}$ partial sum in each node, the value for a as well.

Thus each of my nodes has:

  1. Key = The $i_{th}$ element of the series input.
  2. Sum = The $i_{th}$ partial sum so far.
  3. Val = The value of $a_{i}$ for this node.

By doing that, the operation PartialSum will be identical to Search, thus being in $O(logn)$.

Unfortunately my approach doesn't work so well with change. By storing the partial sums in every node, if a lower node changes, all of the tree's sums are to be recomputed, being in $O(n)$.

I am trying to take a different approach but I'm confused. Can someone HINT me here?


1 Answer 1


Instead of storing the whole $i_{th}$ sum in each node, just store the partial sum of the left sub tree.

  • $\begingroup$ Alternatively, in each node, store the sum of the elements in that subtree. $\endgroup$
    – Pseudonym
    Feb 3, 2015 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.