Тинькофф B' - Дерево Фенвика

Дерево Фенвика - структура данных, дерево на одномерном массиве, которая обладает такими свойствами, как:

1. Сумма на отрезке с L по R
2. Изменение значения в какой-то позиции за O(LogN)
3. Требует O(N) памяти

Код взятия суммы на отрезке: (массив f - наше дерево)

ll get_sum(ll i){
    ll ans = 0;
    for(; i >= 0; i = (i&(i+1))-1){
        ans += f[i];
    }
    return ans;
}


ll sum_otr(ll l, ll r){
    return get_sum(r) - get_sum(l-1);
}

Обновление на точке:

void update(ll i, ll x){
    for(; i < n; i = (i | (i+1))){
        f[i] += x;
    }
}

Так же Дерево Фенвика можно сделать двумерным (подробности - https://e-maxx.ru/algo/fenwick_tree)