Дерево Фенвика

Запрос суммы на отрезке, запрос добавления к отдельному элементу

Пусть имеется массив f[], каждый элемент которого хранит частичную сумму элементов массива a[], а именно а[i] = a[F(i)] + a[F(i) + 1] + ... + a[i - 1] + a[i], где F() — определённая функция.

Тогда сумма от 0 до r вычисляется следующим образом:

int query(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = F(i) - 1)
        res += f[i];
    return res;
}

Пусть F(i) = i & (i + 1):

  i      = xx...x100...011...1 
F(i)     = xx...x100...000...0
F(i) - 1 = xx...x011...111...1

Можно видеть, что каждая операция i = (i & (i + 1)) - 1 будет обнулять в i один единичный разряд, что обеспечит логарифмическую сложность операции суммы.

Если некоторый элемент a[i] изменился, то должны таким же образом измениться все элементы f[j], где F(j) <= i <= j. После некоторых вычислений можно убедиться, что данным ограничениям удовлетворяет индекс i, а также все индексы, получаемые из i последовательностью изменений младшего нулевого разряда на единичный, то есть применений операции i |= (i + 1).

int query(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i];
    return res;
}
void modify(int r, int val) {
    for (int i = r; i < MAX_SIZE; i |= i + 1)
        f[i] += val;
}

int sum(int l, int r) {
    return query(r) - (l ? query(l - 1) : 0);
}
void add(int pos, int val) {
    modify(pos, val);
}

Запрос отдельного элемента, запрос добавления на отрезке

Заменим массив a[] на массив deltaA[] по следующему правилу: deltaA[0] = a[0], deltaA[i] = a[i] - a[i - 1]. Построим дерево Фенвика по массиву deltaA[].

Тогда query(i) равно a[i], а вызов modify(pos, val) добавит val ко всем элементам a[], у которых i >= pos. Следовательно, чтобы увеличить элементы с индексами от l до r, нужно вызвать modify(l, val) и modify(r + 1, -val).

int get(int pos) {
    return query(pos);
}
void add(int l, int r, int val) {
    modify(l, val);
    modify(r + 1, -val);
}

Запрос минимума на отрезке, запрос добавления к отдельному элементу

• Dima M., Ceterchi R. Efficient Range Minimum Queries using Binary Indexed Trees
• neerc.ifmo.ru/wiki — Встречное дерево Фенвика

Запрос суммы на отрезке, запрос добавления на отрезке

Метод P. Mishra

Пусть имеются деревья Фенвика T и Tx, и пусть (Tx.query(i) * i + T.query(i)) — сумма элементов массива a[] от a[0] до a[i]. Далее, пусть элементы массива a[] с индексами от l до r увеличились на величину val. Рассмотрим, как при этом изменится сумма элементов массива a[] от a[0] до a[i]:

• Если i < l, то сумма не изменилась, и значение (Tx.query(i) * i + T.query(i)) ей соответствует.
• Если l <= i <= r, то сумма увеличилась на (val * (i - l + 1)). Следовательно, к ячейкам Tx нужно добавить val, а к ячейкам T — (val * (-l + 1)).
• Если i > r, то сумма увеличилась на (val * (r - l + 1)). Следовательно, ячейки Tx изменять не нужно, а к ячейкам T нужно добавить (val * (r - l + 1)).

int prefixSum(int r) {
    return Tx.query(r) * r + T.query(r);
} 
int sum(int l, int r) {
    return prefixSum(r) - (l ? prefixSum(l - 1) : 0);
}
void add(int l, int r, int val) {
    Tx.modify(l, val);
    Tx.modify(r + 1, -val);         //Tx.modify(r + 1, 0 - val);
    T.modify(l, val * (-l + 1));
    T.modify(r + 1, val * r);       //T.modify(r + 1, (val * (r - l + 1)) - (val * (-l + 1)));
}

• Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays
• petr-mitrichev.blogspot.ru — Fenwick tree range updates
• topcoder.com — How to modify BIT to update the ranges and query the ranges?
• topcoder.com — Range update in BIT
• kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree

Данный метод может быть обобщён на большие размерности: Варианты дерева Фенвика

Метод М. Кормышова

Введём массив fAdd[], i-й элемент которого хранит значение, добавляемое ко всем элементам массива a[] на отрезке F(i)..i.

int query(int r) {
    int res = 0;
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i] + fAdd[i] * (i - (i & (i + 1)) + 1);
    for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
        res += fAdd[i] * (r - (i & (i + 1)) + 1);
    return res;
}
void modify(int r, int val) {
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        fAdd[i] += val;
    for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
        f[i] += val * (r - (i & (i + 1)) + 1);
}

int sum(int l, int r) {
    return query(r) - (l ? query(l - 1) : 0);
}
void add(int l, int r, int val) {
    modify(r, val);
    if (l)
        modify(l - 1, -val);
}

• habrahabr.ru — Дерево Фенвика с модификацией на отрезке.

Ссылки

Теория:

• Варианты дерева Фенвика
• e-maxx.ru — Дерево Фенвика
• neerc.ifmo.ru/wiki — Дерево Фенвика
• brestprog.by — Дерево Фенвика
• algorithmica.org — Дерево Фенвика
• cppalgo.blogspot.com — Дерево Фенвика
• Лахно А. Дерево Фенвика

Демонстрация:

• VisuAlgo — Fenwick Tree

Код:

• CodeLibrary — Fenwick tree
• CodeLibrary — Fenwick tree interval
• Algos — Fenwick tree
• Algos — Fenwick tree 2D

Задачи:

• Задачи: Дерево Фенвика