8

Questions: I have stumbled upon Fenwick trees (Binary index trees) that allow to calculate cumulative sums easily. However, I have only found implementations where the number of leeves (summands) is constant (but their value can change). Is there something like a generalised Fenwick tree that allows for the number of leeves (summands) to change, i.e. to have a variable size?

Background I am currently writing some stochastic simulation code (in C++): There are balls in an urn and each ball i has a certain probability p_i to be drawn. Upon a drawing event a ball is drawn (and removed) and replaced by two new balls with new probabilities (and all probabilities are rescaled accordingly; I do this "rescaling" efficiently already, so don't bother about it). At some point I start to remove balls such that the number of balls fluctuates around a constant value (that is known before). To do the drawing efficiently I want to use a binary tree. The standard Fenwick tree does exactly what I want except that it doesn't allow for the change in number of balls in the urn.

Typical numbers Start with 10 balls, add balls and start to remove balls once there are around 1000 such that there are then between 900 and 1100 balls in the urn (i.e. balls are added and removed such that the number stays around 1000).

Workaround so far Estimate the maximal number of balls needed (with some security margin, say 1200 balls) and make the constant-size Fenwick tree that large with most of the balls initially having probability 0 to be drawn and being successively updated.

Thank you very much for your help! Matthias

4

1 回答 1

12

实际上，正常（不以任何方式概括）Fenwick 树允许随时增加叶子的数量。

某些特定的实现可能不允许它。但这可以解决。例如，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);
    }
}

笔记。

  1. 与 TopCoder 的实现不同（read返回前缀总和），此实现提供后缀总和。如果您需要前缀总和，只需从值的总和中减去返回read的值。
  2. 我选择了这个实现，因为 (1) 它是对著名的 TopCoder 实现的简单修改，并且 (2) 它以非常对称的方式更新索引，因此只需将 '+' 更改为 '-' 即可从前缀获取后缀。
  3. 否则我宁愿在索引计算中使用不同的按位运算。恕我直言，这个博客：Fenwick trees demystified提出了一个更好的选择，每次索引更新只有 2 次操作，而不是 3 次（但还需要一些修改以允许可变大小）。如果兼容性不是问题，我们可以通过使用一些特定的指令来做得更好，比如BLSR最近的英特尔指令集 (BMI1)。
于 2014-02-24T19:09:31.793 回答