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?


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

| cite | improve this answer | |
  • $\begingroup$ Alternatively, in each node, store the sum of the elements in that subtree. $\endgroup$ – Pseudonym Feb 3 '15 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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