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 :)

  • 2
    $\begingroup$ Can you explain what the operations are supposed to do? Try to be more elaborate with the description. $\endgroup$ – Yuval Filmus Oct 9 '14 at 4:38
  • 1
    $\begingroup$ If you use a balanced tree for each key as well as for all values, then all the operations should run in $O(\log n)$. I don't know how you get $O(n\log n)$. Specifically, these operations take $O(\log n)$ in a single balanced tree, so I don't see why your insert operation takes $O(n\log n)$. $\endgroup$ – Yuval Filmus Oct 9 '14 at 4:39

Your Answer

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

Browse other questions tagged or ask your own question.