Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 694
matthse Avatar asked Feb 24 '14 18:02

matthse


People also ask

Is Fenwick tree better than segment tree?

Fenwick trees are faster and extremely simple to implement. The asymptotic bounds are equivalent, but the most basic query and update code is almost branchless, non-recursive, and uses very few operations. The segment tree versions of this can be made almost as fast, but this does take extra effort.

What is the space complexity of Fenwick tree?

Segment Trees require a space complexity of O(4*N) , while fenwick trees only needs O(N) , and so it's also useful when being used as a hash map.

What is Fenwick tree used for?

A Fenwick tree or binary indexed tree is a data structure that helps compute prefix sums efficiently. Computing prefix sums are often important in various other algorithms, not to mention several competitive programming problems. For example, they are used to implement the arithmetic coding algorithm.

Is binary indexed tree same as Fenwick tree?

Binary Indexed Tree also called Fenwick Tree provides a way to represent an array of numbers in an array, allowing prefix sums to be calculated efficiently.


1 Answers

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).
like image 157
Evgeny Kluev Avatar answered Oct 03 '22 09:10

Evgeny Kluev