Is there a data structure that can return the prefix sum of an array, update an element, and insert/remove entries from an array in O(log n)?
“prefix sum” is the sum of all items from the first to the provided index.
For example, given an array of non-negative numbers 8 1 10 7, the prefix sum for the first three components is 19 (8 + 1 + 10). By changing the first element to 7, introducing 3 as the second element, and eliminating the third, we get 7 3 10 7. Again, the prefix total of the first three components would be 20.
There is a Fenwick tree for prefix sum and update. But I’m not sure how to handle the addition/removal in O(log n) with it.
On the other side, there are various binary search trees, such as the Red-black tree, that handle update/insert/remove operations in logarithmic time. But I’m not sure how to keep the supplied ordering while performing the prefix sum in O. (log n).
