Dynamic prefix sum

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

Hi @neon124,

This is not Processing related but you should find some examples of a Fenwick tree implementation in the Wikipedia article:

at least addition of an element

Is it related to the prefix sum problem? I don’t understand what you are trying to achieve :wink:

There are about 31 Java library repos about Fenwick on GitHub.

Plus about 143 wikis on the Fenwick subject for Java.

Btw, Processing’s IDE (PDE) accepts “.java” files which can be imported into a “.pde” sketch.