Дерево Фенвика: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 79: Строка 79:
* [http://github.com/indy256/codelibrary/blob/master/java/src/FenwickTree.java CodeLibrary — Fenwick tree]
* [http://github.com/indy256/codelibrary/blob/master/java/src/FenwickTree.java CodeLibrary — Fenwick tree]
* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos — Fenwick tree]
* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos — Fenwick tree]
* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree2D.cpp Algos — Fenwick tree 2D]


[[Category:Структуры данных для задач RSQ/RMQ]]
[[Category:Структуры данных для задач RSQ/RMQ]]

Версия от 00:30, 11 января 2015

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

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

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

Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то добавим массив 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);
}

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

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

Ссылки