动态(即可变大小)Fenwick树？

Question

问题: 我偶然发现了Fenwick树(二元索引树),它们可以轻松计算累积总和.但是,我只发现了leeves(summands)数量不变的实现(但它们的值可以改变).有没有类似于广义Fenwick树的东西,允许改变leeves(summands)的数量,即具有可变大小？

背景 我正在编写一些随机模拟代码(用C++编写):在一个瓮中有球,每个球我有一定的概率p_i被绘制.在绘图事件中,球被绘制(并被移除)并被具有新概率的两个新球替换(并且相应地重新调整所有概率;我已经有效地"重新缩放",因此不要打扰它).在某些时候,我开始移除球,使得球的数量围绕恒定值(之前已知)波动.为了有效地进行绘图,我想使用二叉树.标准的Fenwick树完全符合我的要求,只是它不允许更改urn中的球数.

典型的数字 从10个球开始,添加球并且一旦有大约1000个就开始移除球,使得在球中有900到1100个球(即球被添加和移除使得数量保持在1000左右).

到目前为止的解决方法 估计所需的最大球数(具有一些安全范围,比如1200个球),并使大小的恒定大小的Fenwick树具有最大概率为0的大部分球被绘制并连续更新.

非常感谢您的帮助!马蒂亚斯

Answer 1

实际上,正常(不以任何方式概括)Fenwick树允许随时增加叶子的数量.

某些特定实现可能不允许它.但这可以修复.例如,从TopCoder实现不允许更改叶子数.问题是update函数修改了从给定索引开始并向上运行的数组元素,当它达到某个limit(MaxVal)时停止,在我们的例子中,这是预先不知道的.read函数迭代向下的数组元素,因此它不需要知道当前的数组大小.如果我们在update和之间交换数组迭代代码read,这个问题可以修复:现在update不需要知道MaxVal,MaxVal用于read,并且我们可以使用最大的更新索引MaxVal.

int read(int idx){
    int sum = 0;
    while (idx <= MaxVal){
        sum += tree[idx];
        idx += (idx & -idx);
    }
    return sum;
}

void update(int idx ,int val){
    while (idx > 0){
        tree[idx] += val;
        idx -= (idx & -idx);
    }
}

笔记.

1. 与TopCoder(read返回前缀sum)的实现不同,此实现提供后缀sum.如果您需要前缀sum,只需从值的总和中减去返回read的值.
2. 我选择了这个实现,因为(1)它是对着名的TopCoder实现的简单修改,(2)它以非常对称的方式更新索引,所以只需将'+'改为' - '就可以从前缀获得后缀.
3. 否则,我宁愿在索引计算中使用不同的按位运算.恕我直言这个博客:Fenwick树揭秘建议一个更好的选择,每个索引更新只有2个操作,而不是3(但也需要一些修改,以允许可变大小).如果兼容性不是问题,我们可以通过使用一些特定指令(如BLSR最近的英特尔指令集(BMI1))做得更好.