Dynamic (i.e. variable size) Fenwick Tree?

Question

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

Answer 1

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

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);
    }
}

Notes.

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