68
правок
Изменения
Нет описания правки
==Пример задачи для двумерного случая==
[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейкиэлементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений нашего рисунка).]]
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
# добавить точку в <tex>(x, y)</tex>;
==Псевдокод==
t {{---}} массив, в котором хранится наше дерево Фенвика.
<code style = "display: inline-block;">
'''int''' sum(x: '''int''', y: '''int'''):
'''int''' result = 0
==Источники информации==
*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Binary Indexed Trees]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево Фенвика]]
[[Категория: Структуры данных]]
