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?
Efficient deletion in Fenwick tree
data structures;binary trees