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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Запрос на отрезке и модификация отдельных элементов ==
== Запрос суммы на отрезке, запрос добавления к отдельному элементу ==


Пусть каждый элемент массива <tt>b[]</tt> хранит частичную сумму элементов массива <tt>a[]</tt>, а именно <tt>b[i] = a[f(i)] + a[f(i) + 1] + ... + a[i - 1] + a[i]</tt>, где <tt>f()</tt> &mdash; определённая функция.
Пусть имеется массив f[], каждый элемент которого хранит частичную сумму элементов массива a[], а именно а[i] = a[F(i)] + a[F(i) + 1] + ... + a[i - 1] + a[i], где F() &mdash; определённая функция.


Тогда сумма от <tt>1</tt> до <tt>r</tt> вычисляется следующим образом:
Тогда сумма от 0 до r вычисляется следующим образом:
  int sum(int r) {
  int query(int r) {
     int res = 0;
     int res = 0;
     for (int i = r; i >= 0; i = f(i) - 1)
     for (int i = r; i >= 0; i = F(i) - 1)
         res += b[i];
         res += f[i];
     return res;
     return res;
  }
  }


Пусть <tt>f(i) = <b>i & (i + 1)</b></tt>:  
Пусть F(i) = <b>i & (i + 1)</b>:  
   i      = xx...x100...011...1  
   i      = xx...x100...011...1  
  f(i)    = xx...x100...000...0
  F(i)    = xx...x100...000...0
  f(i) - 1 = xx...x011...111...1
  F(i) - 1 = xx...x011...111...1
Можно видеть, что каждая операция <tt>i = (i & (i + 1)) - 1</tt> будет обнулять в <tt>i</tt> один единичный разряд, что обеспечит логарифмическую сложность операции суммы.
Можно видеть, что каждая операция i = (i & (i + 1)) - 1 будет обнулять в i один единичный разряд, что обеспечит логарифмическую сложность операции суммы.


Если некоторый элемент <tt>a[i]</tt> изменился, то должны таким же образом измениться все элементы <tt>b[j]</tt>, где <tt>f(j) <= i <= j</tt>. После некоторых вычислений можно убедиться, что данным ограничениям удовлетворяет индекс <tt>i</tt>, а также все индексы, получаемые из <tt>i</tt> последовательностью изменений младшего нулевого разряда на единичный, то есть применений операции <tt><b>i |= (i + 1)</b></tt>.
Если некоторый элемент a[i] изменился, то должны таким же образом измениться все элементы f[j], где F(j) <= i <= j. После некоторых вычислений можно убедиться, что данным ограничениям удовлетворяет индекс i, а также все индексы, получаемые из i последовательностью изменений младшего нулевого разряда на единичный, то есть применений операции <b>i |= (i + 1)</b>.


  int sum(int r) {
  int query(int r) {
     int res = 0;
     int res = 0;
     for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
     for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
         res += b[i];
         res += f[i];
     return res;
     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) {
  int sum(int l, int r) {
     return sum(r) - sum(l - 1);
     return query(r) - (l ? query(l - 1) : 0);
  }
  }
  void add(int pos, int val) {
  void add(int pos, int val) {
     for (int i = pos; i < MAX_SIZE; i |= i + 1)
     modify(pos, val);
        b[i] += 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);
}


Ниже приведён другой подход, описанный М. Кормышовым ([http://habrahabr.ru/post/170933/ habrahabr.ru &mdash; Дерево Фенвика с модификацией на отрезке]).
== Запрос минимума на отрезке, запрос добавления к отдельному элементу ==
* [http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf Dima M., Ceterchi R. Efficient Range Minimum Queries using Binary Indexed Trees]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%81%D1%82%D1%80%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%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 &mdash; Встречное дерево Фенвика]


Если в задаче требуется и подсчитывать сумму, и производить прибавление на отрезке, то добавим массив <tt>bAdd[]</tt>, <tt>i</tt>-й элемент которого хранит значение, добавляемое ко всем элементам массива <tt>a[]</tt> на отрезке <tt>f(i)..i</tt>.
== Запрос суммы на отрезке, запрос добавления на отрезке ==


  int sum(int r) {
=== Метод P. Mishra ===
 
Пусть имеются деревья Фенвика T и Tx, и пусть (Tx.query(i) * i + T.query(i)) &mdash; сумма элементов массива 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 &mdash; (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)));
}
 
* [http://arxiv.org/pdf/1311.6093v4.pdf Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays]
* [http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html petr-mitrichev.blogspot.ru &mdash; Fenwick tree range updates]
* [http://apps.topcoder.com/forums/?module=Thread&threadID=756271 topcoder.com &mdash; How to modify BIT to update the ranges and query the ranges?]
* [http://apps.topcoder.com/forums/?module=Thread&threadID=715842 topcoder.com &mdash; Range update in BIT]
* [http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree kartikkukreja.wordpress.com &mdash; Range updates with BIT / Fenwick Tree]
 
Данный метод может быть обобщён на большие размерности: [[Варианты дерева Фенвика]]
 
=== Метод М. Кормышова ===
 
Введём массив fAdd[], i-й элемент которого хранит значение, добавляемое ко всем элементам массива a[] на отрезке F(i)..i.
 
int query(int r) {
     int res = 0;
     int res = 0;
     for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
     for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
         res += b[i] + bAdd[i] * (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)
     for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
         res += bAdd[i] * (r - (i & (i + 1)) + 1);
         res += fAdd[i] * (r - (i & (i + 1)) + 1);
     return res;
     return res;
  }
  }
int sum(int l, int r) {
  void modify(int r, int val) {
    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)
     for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
         bAdd[i] += val;
         fAdd[i] += val;
     for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
     for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
         b[i] += val * (r - (i & (i + 1)) + 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) {
  void add(int l, int r, int val) {
     add(r, val);
     modify(r, val);
     if (l)
     if (l)
         add(l - 1, -val);
         modify(l - 1, -val);
  }
  }


== Ссылки на задачи ==
* [http://habrahabr.ru/post/170933/ habrahabr.ru &mdash; Дерево Фенвика с модификацией на отрезке].
* [http://acmp.ru/?main=task&id_task=307 ACMP #307 &mdash; Атлеты] (Двумерное дерево Фенвика)
* [http://acm.timus.ru/problem.aspx?num=1028 Timus #1028 &mdash; Stars] (Базовая реализация)
* [http://codeforces.ru/gym/100098/problem/B Codeforces #100098.B &mdash; Точки на плоскости] (Двумерное дерево Фенвика)


== Ссылки ==
== Ссылки ==
* [[Дерево Фенвика с модификацией на отрезке]]
Теория:
* [[Варианты дерева Фенвика]]
:* [[Варианты дерева Фенвика]]
* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru &mdash; Дерево Фенвика]
:* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru Дерево Фенвика]
* [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 &mdash; Дерево Фенвика]
:* [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 &mdash; Дерево Фенвика]
* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com &mdash; Дерево Фенвика]
:* [https://brestprog.by/topics/fenwicktree/ brestprog.by — Дерево Фенвика]
* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru &mdash; Курс &laquo;Структуры данных&raquo; &mdash; часть 6]
:* [https://algorithmica.org/ru/fenwick algorithmica.org — Дерево Фенвика]
* [http://ejudge.btty.su/bmstu/addon/docs/articles/sbory2006-fenvik.pdf Лахно А. Дерево Фенвика]
:* [http://cppalgo.blogspot.ru/2011/02/fenwick-tree.html cppalgo.blogspot.com Дерево Фенвика]
* [http://visualgo.net/bit.html VisuAlgo &mdash; Binary Indexed Tree]
:* [https://informatics.mccme.ru/mod/book/view.php?id=491&chapterid=182 Лахно А. Дерево Фенвика]
* [http://github.com/indy256/codelibrary/blob/master/java/src/FenwickTree.java CodeLibrary &mdash; Fenwick tree]
Демонстрация:
* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree.cpp Algos &mdash; Fenwick tree]
:* [https://visualgo.net/en/fenwicktree VisuAlgo — Fenwick Tree]
* [http://github.com/ADJA/algos/blob/master/DataStructures/FenwickTree2D.cpp Algos &mdash; Fenwick tree 2D]
Код:
:* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/fenwick_tree.cpp CodeLibrary — Fenwick tree]
:* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/fenwick_tree_interval.cpp CodeLibrary Fenwick tree interval]
:* [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]]

Текущая версия от 12:19, 11 сентября 2020

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

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

Ссылки

Теория:

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

Код:

Задачи: