Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way to delete A[index] and update the values accordingly in F[] would be to perform update(index, -A[index]), then set A[index]=0. However, I could imagine that after a few deletes, the tree would be quite inefficient with all the 0s floating around.

We could compress the tree at each deletion by shifting the values down in A[] after A[index]=0 and rebuilding F[index:n] by referencing A. However, this solution is worst case O(nlogn) time, and I feel like if there was a way to rebuild F[index:n] using values in F[], this could be much more efficient. Unfortunately, the literature online seems a bit sparse on the deletion front. Any ideas?

  • $\begingroup$ You can construct F(A) in linear time, right? Can you then amortize away all the deletions? If there are $n$ deletions, you build a new tree without the deleted elements, charge the deleted elements. $\endgroup$ – Pål GD Mar 19 '15 at 9:22

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.