Изменения

Перейти к: навигация, поиск

Многомерное дерево Фенвика

349 байт добавлено, 22:52, 7 июня 2011
→‎Пример задачи для двумерного случая
==Пример задачи для двумерного случая==
[[Файл:example42.gif |thumb|600px|right |Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейки, которые обновятся при изменении ячейки <tex>(5, 3)</tex>]]
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
# добавить точку в <tex>(x, y)</tex>;
</code>
[[Файл:example42.gif]] <br/>Пример дерева Фенвика Чтобы посчитать значение функции для прямоугольника <tex>(16 \times 8x_1, y_1), (x_2, y_2)</tex>нужно воспользоваться формулой включения-исключения. Синим обозначены ячейки, которые обновятся при изменении ячейки Например для суммы: <tex>s = sum(x_2,y_2)-sum(x_2,y_1)-sum(x_1,y_2)+sum(5x_1, 3y_1)</tex>
== Полезные ссылки: ==
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/9294»

Навигация