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

Запрос на отрезке и модификация отдельных элементов

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

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

int sum(int r) {
    int res = 0;
    for (int i = r; i > 0; i = f(i) - 1)
        res += b[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] изменился, то должны таким же образом измениться все элементы b[j], где f(j) <= i <= j. После некоторых вычислений можно убедиться, что данным ограничениям удовлетворяет индекс i, а также все индексы, получаемые из i последовательностью изменений младшего нулевого разряда на единичный, то есть применений операции i |= (i + 1).

int sum(int r) {
    int res = 0;
    for (int i = r; i > 0; i = (i & (i + 1)) - 1)
        res += b[i];
    return res;
}
int sum(int l, int r) {
    return sum(r) - sum(l - 1);
}
void add(int pos, int val) {
    for (int i = pos; i < MAX_SIZE; i |= i + 1)
       b[i] += val;
}

Запрос на отрезке и модификация на отрезке

Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то добавим массив add[], i-й элемент которого хранит значение, добавляемое ко всем элементам массива a[] на отрезке f(i)..i.

int sum(int r) {
    int res = 0;
    for (int i = r; i > 0; i = (i & (i + 1)) - 1)
        res += b[i] + add[i] * (i - (i & (i + 1)) + 1);
    for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
        res += add[i] * (i - (i & (i + 1)) + 1);
    return res;
}
int sum(int l, int r) {
    return sum(r) - sum(l - 1);
}
void add(int r, int val) {
    for (int i = r; i > 0; i = (i & (i + 1)) - 1)
       add[i] += val;
    for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
       b[i] += val * (i - (i & (i + 1)) + 1);
}
void add(int l, int r, int val) {
    add(r, val);
    add(l - 1, -val);
}

Также возможен другой подход к реализации обновления на отрезке; он описан в подстатье Дерево Фенвика с модификацией на отрезке.

Ссылки на задачи

• ACMP #307 — Атлеты

Ссылки

• e-maxx.ru — Дерево Фенвика
• neerc.ifmo.ru/wiki — Дерево Фенвика
• cppalgo.blogspot.com — Дерево Фенвика
• habrahabr.ru — Дерево Фенвика с модификацией на отрезке
• informatics.mccme.ru — Курс «Структуры данных» — часть 6
• Лахно А. Дерево Фенвика
• VisuAlgo — Binary Indexed Tree
• CodeLibrary — Fenwick tree
• Algos — Fenwick tree