我计划在 Java中实现一个非固定大小的Fenwick 树。即，允许通过添加/删除元素来交叉范围查询的 Fenwick 树。
到目前为止，我看到的所有实现和示例都是针对固定大小的 Fenwick 树，其中元素的数量在预处理频率之前是已知的。它们使用固定大小的数组，因此在预处理完成后无法添加或删除元素。（嗯，这是可能的，但我需要重新构建结构）。
我想过扩展TreeMap或可能AbstractMap，但TreeMap实际上是一棵红黑树，我不知道如何在不丢失重新平衡过程中涉及的节点的累积和的情况下实现红黑机制（使树保持平衡） .
所以我想也许我应该采取另一种方法：为什么不扩展或调整一个简单的随机访问ArrayList并在调整基础数组大小时重新计算所有累积和？这当然会产生影响，但是，嘿，这正是 aHashMap所做的。
这就是为什么我想先在这里问一下，以防有人已经这样做了，并检查您认为哪种方法最好。