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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

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

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

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

Наиболее распространённый подход к реализации обновления на отрезке описан в подстатье Дерево Фенвика с модификацией на отрезке.

Ниже приведён другой подход, описанный М. Кормышовым (habrahabr.ru — Дерево Фенвика с модификацией на отрезке).

Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то добавим массив bAdd[], 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] + bAdd[i] * (i - (i & (i + 1)) + 1);
    for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
        res += bAdd[i] * (r - (i & (i + 1)) + 1);
    return res;
}
int sum(int l, int r) {
    return sum(r) - (l ? sum(l - 1) : 0);
}
void add(int r, int val) {
    for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
        bAdd[i] += val;
    for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
        b[i] += val * (r - (i & (i + 1)) + 1);
}
void add(int l, int r, int val) {
    add(r, val);
    if (l)
        add(l - 1, -val);
}

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

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Дерево_Фенвика&oldid=1990