3.29

In each node of a binary tree store the sub tree sum for the left sub tree.

1. Add : while descending the tree to the left update the sub tree sum by adding the value
2. Insert : same as add, only now we have to add a new node too. To guaranty $O(n\log n)$ times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in $O(1)$ during rotation operations.
3. Delete : When the deleted element has at most 1 child, we only need to update the nodes ancestors. If there are two children, we also need to update elements on the path between the deleted element and it's successor. (The element with which we will swap it before deleting.)
4. Partial sum : With the left sub tree sum values stored in the nodes this operation only involves searching for the element with the specified key, and summing sub tree sums along the way.

Back to Chapter 3