Geek asks and answers

Dynamic (i.e. Variable Size) Fenwick Tree?

Questions: I came across Fenwick trees (binary index trees) that make it easy to calculate aggregate amounts. However, I only found implementations where the number of lees (terms) is constant (but their value can change). Is there something like a generalized Fenwick tree that allows you to change the number of lees (terms), i.e. have a variable size?

Background I am currently writing stochastic modeling code (in C ++): there are balls in the ballot box, and each ball I have a certain probability p_i. When drawing, the ball is drawn (and deleted) and replaced with two new balls with new probabilities (and all probabilities are scaled accordingly, I do this “scaling” effectively already, so don't worry about that). At some point, I begin to remove the balls so that the number of balls fluctuates around a constant value (which was previously known). To make a drawing efficiently, I want to use a binary tree. The standard Fenwick tree does exactly what I want, except that it does not allow changing the number of balls in the urn.

Typical numbers Start with 10 balls, add balls and start removing balls when there are about 1000, so there are from 900 to 1100 balls in the ballot box (i.e., Balls are added and removed so that the number remains around 1000).

Workaround Estimate the maximum number of balls needed (with some margin of safety, say, 1200 balls) and make a Fenwick tree with a constant size that will be large, with most of the balls initially having a probability of 0 will be drawn and updated sequentially.

Many thanks for your help! Matthias

+5
source share
2 answers

In fact, a normal (not generalized in any way) Fenwick tree allows you to increase the number of leaves at any time.

. . , 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) , "+" "-" .
  • . IMHO : , 2 , 3 ( , ). , , , BLSR Intel (BMI1).
+6

@

！ , Fenwick Tree Dynamic Like Fenwick Tree

0

More articles:


All Articles