c++ - 动态(即大小可变)的Fenwick树？

问题:
我偶然发现了Fenwick树(二叉索引树)，它们可以轻松地计算累积总和。但是，我仅发现实现中，leeves(求和数)的数量是恒定的(但是它们的值可以改变)。 是否有像通用的Fenwick树之类的东西，它允许改变后备身材的数量(即需求量)，即具有可变的大小？

背景
我目前正在编写一些随机模拟代码(在C++中):中有多个球，每个球i都有一定的概率p_i被绘制。在绘制事件中，一个球被绘制(并移除)，并被两个具有新概率的新球替换(并且所有概率都被相应地缩放；我已经高效地执行了“缩放”，因此不必理会)。在某个时候，我开始移除球，以使球的数量围绕恒定值波动(之前知道)。为了有效地进行绘图，我想使用二叉树。标准的Fenwick树完全符合我的要求，只是它不允许更改骨灰盒中球的数量。

典型数字
从10个球开始，添加球，一旦大约1000个球就开始移除球，这样骨灰盒中就会有900到1100个球(即添加和移除球，使得数量保持在1000个左右)。

到目前为止的解决方法
估计所需的最大球数(有一定的安全余量，例如1200个球)，并使恒定大小的Fenwick树变大，其中大多数球最初被绘制为0并被连续更新的概率。

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

最佳答案

实际上，普通(不以任何方式概括)的Fenwick树允许随时增加叶子数量。

一些特定的实现可能不允许这样做。但这可能是固定的。例如，implementation from TopCoder不允许更改叶子数。问题在于update函数会修改从给定索引开始并向上的数组元素，并在达到某个限制(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);
    }
}

笔记。

与TopCoder的实现(read返回前缀和)不同，此实现提供后缀和。如果需要前缀总和，只需从总值中减去read返回的值即可。

我选择此实现是因为(1)它是对著名TopCoder实现的简单修改，并且(2)它以非常对称的方式更新索引，因此只需将'+'更改为'-'就可以了。后缀的前缀。

否则，我希望在索引计算中使用不同的按位运算。恕我直言，此博客:Fenwick trees demystified是一个更好的选择，每个索引更新仅进行2个操作，而不是3个(但还需要进行一些修改以允许可变大小)。如果不考虑兼容性，我们可以通过使用一些特定的指令来做得更好，例如最近的英特尔指令集(BMI1)中的BLSR。

关于c++ - 动态(即大小可变)的Fenwick树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21995930/