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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 73: Строка 73:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.A4.D0.B5.D0.BD.D0.B2.D0.B8.D0.BA.D0.B0 neerc.ifmo.ru/wiki — Дерево Фенвика]
* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]
* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com — Дерево Фенвика]
* [http://habrahabr.ru/post/170933/ habrahabr.ru — Дерево Фенвика с модификацией на отрезке]
* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 6]
* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 6]
* [http://ejudge.btty.su/bmstu/addon/docs/articles/sbory2006-fenvik.pdf Лахно А. Дерево Фенвика]
* [http://ejudge.btty.su/bmstu/addon/docs/articles/sbory2006-fenvik.pdf Лахно А. Дерево Фенвика]

Версия от 11:29, 21 мая 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);
}

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

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

Ссылки