动态（即可变大小）分域树？ [英] Dynamic (i.e. variable size) Fenwick Tree?

问题描述

问题： 我曾偶然发现了分域树（二进制索引树），允许容易计算累计总和。不过，我只找到实现其中leeves（被加数）的数量是恒定的（但它们的值可以改变）。 有什么样一个通用树状数组，允许的leeves（被加数）的数量发生变化，即具有可变大小？

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?

背景 我目前正在写一些随机模拟code（在C ++）：有球的骨灰盒，并绘制每个球我有一定的概率p_i。当一个绘图事件球绘制（和删除），通过两个新球，新更换的概率（和所有的概率也相应重新调整，我这样做是重新调整有效了，所以不用理会）。在某些时候我开始删除球，使得滚珠数围绕恒定值波动（即前已知的）。要做到绘图效率我想用一个二叉树。标准分域树不正是我想要的只是它不允许在球数的变化，在瓮。

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.

典型值 开始10个球，添加球并开始一旦除去球有大约1000使得有然后900至1100球在瓮（即球添加和删除，使得数保持1000左右）。

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).

解决方法为止 估计所需的球的最大数量（与一些安全余量，说1200球），使固定尺寸树状数组，大型与大多数球的初始具有0概率要绘制与被依次更新。

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

推荐答案

其实，正常（不以任何方式广义）分域目录树中，增加叶片数在任何时间。

Actually, normal (not generalized in any way) Fenwick tree allows increasing the number of leaves at any time.

某些特定的实现可能不答应。但是这可能是固定的。例如，从顶部codeR实施< /一>不允许叶子的数量来改变。问题是，更新函数修改数组元素，从给定的指标出发，走上坡路，当达到某一限度停止（MaxVal最大值 >），这在我们的情况下，事先是不知道。 读函数遍历数组元素开始向下，所以它并不需要知道当前数组的大小。如果我们换间更新和读，这个问题可能是固定的阵列迭代code：现在更新并不需要知道 MaxVal最大值， MaxVal最大值用在读，我们可以使用最大更新的索引，只要 MaxVal最大值。

Some particular implementation may not allow it. But this could be fixed. For example, implementation from TopCoder does not allow the number of leaves to change. The problem is that update function modifies array elements starting from given index and going upwards, stopping when it reaches some limit (MaxVal), which in our case is not known in advance. read function iterates array elements going downwards, so it does not need to know current array size. If we swap array iteration code between update and read, this problem could be fixed: now update does not need to know MaxVal, MaxVal is used in read, and we could use the largest updated index so far as 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. 不同于从顶部codeR实现（其中读返回preFIX总和），此实现提供后缀总和。如果您需要preFIX总和，只是减去由返回值读取从值的总和。
2. 在我选择这个实现是因为（1）它是著名的上衣codeR的实现，一个简单的修改（2）它更新非常对称的方式索引，所以它足以只是改变'+'来' - '。从preFIX得到后缀
3. 否则我会preFER在指数计算中采用不同的位操作。恕我直言，这个博客：分域树揭秘提出了一个更好的选择，与每个索引更新只有2的操作，而不是3（还需要进行一些修改，以允许可变大小）。如果兼容性不是一个问题，我们能做的，甚至通过使用最新的Intel指令集（BMI1），如 BLSR 一些具体的说明比较好。

1. Unlike implementation from TopCoder (where read returns prefix sum), this implementation gives suffix sum. If you need prefix sum, just subtract value returned by read from total sum of values.
2. I've chosen this implementation because (1) it is a simple modification of well-known TopCoder's implementation and (2) it updates indexes in very symmetrical way, so it's enough just to change '+' to '-' to get from prefix to suffix.
3. Otherwise I would prefer to use different bitwise operations in index calculations. IMHO this blog: Fenwick trees demystified suggests a better alternative, with only 2 operations per index update, instead of 3 (but also needs some modifications to allow variable size). If compatibility is not a concern, we could do even better by using some specific instructions like BLSR from recent Intel's instruction set (BMI1).

这篇关于动态（即可变大小）分域树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！