java非固定大小Fenwick树实现

Question

我计划在Java中实现一个非固定大小的Fenwick tree。也就是说，Fenwick树允许使用添加/删除元素交错范围查询

到目前为止，我所看到的所有implementations和samples都是固定大小的芬威克树，在预处理频率之前，元素的数量是已知的。它们使用固定大小的数组，因此在预处理完成后不可能添加或删除元素。（嗯，这是可能的，但我需要重建结构）

我曾想过扩展TreeMap或AbstractMap，但由于TreeMap实际上是一棵红黑树，我不知道如何实现红黑机制（使树保持平衡）而不丢失重新平衡过程中涉及的节点的累积和

所以我想也许我应该采取另一种方法：为什么不扩展或调整一个简单的随机访问ArrayList，并在调整基础数组的大小时重新计算所有累积和？这当然会产生影响，但是，嘿，这正是HashMap所做的

这就是为什么我想在这里先问一下，以防有人已经这样做了，并检查你认为哪种方法是最好的