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.
- Unlike implementation from TopCoder (where
read
returns prefix sum), this implementation gives suffix sum. If you need prefix sum, just subtract value returned byread
from total sum of values. - 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.
- 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).