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

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

Пусть каждый элемент массива 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;
}

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

Если в задаче требуется производить изменения на отрезке и возвращать значения отдельных элементов, то пусть массив a[] хранит не сами элементы, а разности текущего и предыдущего элементов. Тогда, чтобы увеличить все элементы на отрезке l..r на величину val, достаточно добавить val к a[l] и добавить -val к a[r + 1] (две операции add), а чтобы вывести фактическое значение элемента в позиции pos, достаточно вернуть сумму a[1] + a[2] + ... + a[pos] (операция sum).

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

Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то поступим следующим образом. Во-первых, пусть имеют место все соображения, изложенные в предыдущем абзаце. Далее, пусть сумма на отрезке 1..r выражается как a[r] * r - a1[r]. Осталось понять, как будут изменяться элементы a1[] при обновлениях на отрезках a[]. Пусть ко всем элементам a[] на отрезке l..r добавлено значение val. Рассмотрим значение суммы элементов a[] на отрезке 1..pos:

• Если pos < l, то реальная сумма не изменилась, а сумма, рассчитываемая по указанной выше формуле, также не изменилась и соответствует реальной;
• Если l <= pos <= r, то к реальной сумме добавится (val * (p - l + 1)), а к сумме, рассчитываемой по указанной ранее формуле, — (val * pos). Чтобы расчётное значение соответствовало реальному, ко всем элементам a1[] с индексами не меньше l нужно добавить (val * (l - 1));
• Если r < pos, то к реальной сумме добавится (val * (r - l + 1)), а к сумме, рассчитываемой по указанной ранее формуле, — ничего. Чтобы расчётное значение соответствовало реальному, от всех элементов a1[] с индексами больше r нужно отнять (val * (r - l + 1)), то есть прибавить к ним (val * (l - 1 - r));

Можно видеть, что операции над массивом a1[] можно реализовать с помощью второго дерева Фенвика:

• Добавление значения val на отрезке l..r: updateA(l, val); updateA(r + 1, -val); updateA1(l, val * (l - 1)); updateA1(r + 1, -val * r);
• Подсчёт суммы на отрезке 1..r: sumA(r) * r - sumA1(r);

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

• ACMP #307 — Атлеты

Ссылки

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