43
правки
Изменения
Нет описания правки
{{Определение|definition='''Многомерное [[Дерево дерево Фенвика]] легко обобщается ''' - структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)# изменять значение любого элемента в k-мерном массиве;# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на многомерный случайk-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.}}
==Пример задачи для двумерного случая==
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
# добавить точку в <tex>(x, y)</tex>;
# удалить точку из <tex>(x, y)</tex>;
# посчитать количество точек в прямоугольнике <tex>(0, 0), (x, y)</tex>;
m - количество точек, maxX - максимальная x координата, maxY - максимальная y координата.тогда дерево строится за <tex>O(m * \log (maxX) * \log (maxY))</tex>, а запросы выполняются за <tex>O(\log (maxX) * \log (maxY))</tex> Добавляя точку вызовем <tex>inc(x, y, 1)</tex>, а удаляя <tex>inc(x, y, -1)</tex>. Таким образом запрос <tex>sum(x, y)</tex> дает количество точек в прямоугольнике. ''Пример реализации для двумерного случая:''
<code>
