Динамический (т.е. переменный размер) Fenwick Tree?

Собственно, нормальное (никак не обобщенное) дерево Фенвика позволяет в любое время увеличить количество листьев.

Некоторые конкретные реализации могут не допустить этого. Но это можно исправить. Например, реализация от 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);
}
}

Заметки.

1. В отличие от реализации из TopCoder (где read возвращает префиксную сумму), эта реализация дает суффиксную сумму. Если вам нужна префиксная сумма, просто вычтите значение, возвращаемое read от общей суммы значений.
2. Я выбрал эту реализацию, потому что (1) это простая модификация хорошо известной реализации TopCoder и (2) она обновляет индексы очень симметричным способом, поэтому достаточно просто изменить «+» на «-», чтобы получить из префикса суффикс.
3. В противном случае я бы предпочел использовать разные побитовые операции в вычислениях индекса. ИМХО это блог: Деревья Фенвика демистифицированы предлагает лучшую альтернативу, с только 2 операциями на обновление индекса вместо 3 (но также требует некоторых модификаций, чтобы разрешить переменный размер). Если совместимость не является проблемой, мы могли бы сделать еще лучше, используя некоторые конкретные инструкции, такие как BLSR из недавнего набора инструкций Intel (BMI1).