I'm planning to implement a non-fixed-size Fenwick tree. That is, a Fenwick tree that allows interleaving range queries with adding/removing elements.
All implementations and samples I've seen so far are for fixed-size Fenwick trees, where the number of elements is known before preprocessing the frequencies. They use a fixed size array, so it's not possible to add or remove elements after preprocessing is done. (Well, it is possible, but I'd need to re-build the structure).
I thought of extending
TreeMap or maybe
AbstractMap, but as
TreeMap is actually a red-black tree, I don't know how to implement the red-black mechanics (so that the tree remains balanced) without loosing the cumulative sums of nodes involved in the rebalancing process.
So I thought that maybe I should take another approach: why not extend or adapt a simple random access
ArrayList and re-calculate all cumulative sums when the underlying array is resized? This would of course have an impact but, hey, that's exactly what a
This is why I wanted to ask here first, in case someone has already done it, and to check which approach you think is the best.