[Solved]: How to efficiently use an AVL tree to store partial sums?

Problem Detail: 

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?

Asked By : JOX

Answered By : JOX

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37914