问题: 我偶然发现了Fenwick树(二元索引树),它们可以轻松计算累积总和.但是,我只发现了leeves(summands)数量不变的实现(但它们的值可以改变).有没有类似于广义Fenwick树的东西,允许改变leeves(summands)的数量,即具有可变大小？
背景 我正在编写一些随机模拟代码(用C++编写):在一个瓮中有球,每个球我有一定的概率p_i被绘制.在绘图事件中,球被绘制(并被移除)并被具有新概率的两个新球替换(并且相应地重新调整所有概率;我已经有效地"重新缩放",因此不要打扰它).在某些时候,我开始移除球,使得球的数量围绕恒定值(之前已知)波动.为了有效地进行绘图,我想使用二叉树.标准的Fenwick树完全符合我的要求,只是它不允许更改urn中的球数.
典型的数字 从10个球开始,添加球并且一旦有大约1000个就开始移除球,使得在球中有900到1100个球(即球被添加和移除使得数量保持在1000左右).
到目前为止的解决方法 估计所需的最大球数(具有一些安全范围,比如1200个球),并使大小的恒定大小的Fenwick树具有最大概率为0的大部分球被绘制并连续更新.
非常感谢您的帮助!马蒂亚斯