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:
- Key = The $i_{th}$ element of the series input.
- Sum = The $i_{th}$ partial sum so far.
- 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
