# Dynamic prefix sum
**URL:** https://discourse.processing.org/t/dynamic-prefix-sum/40421
**Category:** Coding Questions
**Created:** [January 3, 2023, 7:59am UTC](https://discourse.processing.org/t/dynamic-prefix-sum/40421 "2023-01-03T07:59:41Z")
**Posts on this page:** 3
**Page:** 1
### Author:  [@neon124](https://discourse.processing.org/u/neon124)
#### Post date: [January 3, 2023, 7:59am UTC](https://discourse.processing.org/t/dynamic-prefix-sum/40421/1 "2023-01-03T07:59:41Z")
Is there a data structure that can return the [prefix sum](https://www.scaler.com/topics/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](http://en.wikipedia.org/wiki/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).
---
### Author:  [@josephh](https://discourse.processing.org/u/josephh)
#### Post date: [January 3, 2023, 8:55pm UTC](https://discourse.processing.org/t/dynamic-prefix-sum/40421/2 "2023-01-03T20:55:46Z")
Hi @neon124,
This is not Processing related but you should find some examples of a Fenwick tree implementation in the Wikipedia article:
> **[Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree#Implementation_in_C++)**
>
> A Fenwick tree or binary indexed tree (BIT) is a data structure that can efficiently update values and calculate prefix sums in an array of values.
> This structure was proposed by Boris Ryabko in 1989
> with a further modification published in 1992.
> It has subsequently become known under the name Fenwick tree after Peter Fenwick, who described this structure in his 1994 article.
> When compared with a flat array of values, the Fenwick tree achieves a much better balance between two operations: value...
at least addition of an element
> [@neon124](#):
>
> 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).
Is it related to the prefix sum problem? I don’t understand what you are trying to achieve 😉
---
### Author:  [@GoToLoop](https://discourse.processing.org/u/GoToLoop)
#### Post date: [January 3, 2023, 10:24pm UTC](https://discourse.processing.org/t/dynamic-prefix-sum/40421/3 "2023-01-03T22:24:53Z")
There are about 31 Java library repos about Fenwick on [GitHub](https://github.com/search?l=Java&q=Fenwick&type=Repositories).
Plus about 143 [wikis](https://github.com/search?l=Java&q=Fenwick&type=wikis) on the Fenwick subject for Java.
Btw, Processing’s IDE (PDE) accepts “.java” files which can be imported into a “.pde” sketch.