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[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?