1632
правки
Изменения
м
[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений данного рисунка).]]
rollbackEdits.php mass rollback
==Пример задачи для двумерного случая==
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
# добавить точку в <tex>(x, y)</tex>;
Добавляя точку вызовем <tex>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex> дает количество точек в прямоугольнике.
[[Файл:example42.gif |thumb|600px|center|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений данного рисунка).]]
==Псевдокод==
<tex>\mathtt{t }</tex> {{---}} массив, в котором хранится дерево Фенвика.
<code style = "display: inline-block;">
'''int''' sum(x: '''int''', y: '''int'''):
====Обобщение на большие размерности====
Дерево Фенвика относится к структурам данных, не требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
==См. также==
*[http://e-maxx.ru/algo/fenwick_tree [Дерево Фенвика]]* [[Встречное дерево Фенвика]]* [[Дерево Фенвика для некоммутативных операций]]
==Источники информации==
*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Topcoder {{---}} Binary Indexed Trees]
*[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Модификации структур данных]]
