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

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

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

Пусть имеется массив 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);
}

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

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

Метод 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)));
}

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

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

Введём массив 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);
}

Ссылки

Теория:

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

Код:

Задачи: