I approached this problem where I have to write an add(key, value), insert(key, value), delete(key,value) and partial_sum(value) which reports the sum of all the elements in the structure that are larger than 'value'.
This was my attempt at the solution, which works! But sadly it runs at O(nlogn) instead of O(logn).. Is there a way I could optimize this?
My approach - binary tree and in each node of it store the sub tree sum for the left sub tree Add: while descending the tree to the left, update the sub tree sum by adding the value Insert: like add, but also adds a new node (the O(nlogn) comes from using any balanced tree type). And to worry about the sub tree sums I can use an AVL tree, since balancing operations are 3 rotations and the left sub tree sum values can be mantained in O(1) during rotations.. Correct? Delete: When the deleted element has a max of 1 child, only the node ancestors are updated. Two children and it also needs to update elements on the path between the deleted one and the successor. Partial sum: Since the left sub tree sum values are stored in the nodes, it just needs to search for the element with the specific key and sum sub tree sums along the way.
Any suggestions/improvements? Thank you so much :)