Многомерное дерево Фенвика — различия между версиями
Shersh (обсуждение | вклад) м |
Shersh (обсуждение | вклад) м (→Обобщение на большие размерности) |
||
Строка 44: | Строка 44: | ||
====Обобщение на большие размерности==== | ====Обобщение на большие размерности==== | ||
− | Дерево Фенвика относится к структурам данных, | + | Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы. |
+ | |||
==См. также== | ==См. также== | ||
*[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] | *[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] |
Версия 10:25, 8 июня 2015
Определение: |
Многомерное дерево Фенвика (англ. Multidimensional Binary Indexed Tree) — структура данных, требующая памяти и позволяющая эффективно (за )
|
Рассмотрим для начала дерево Фенвика на примере k-мерного массива с
, а затем посмотрим, как можно обобщить его на большие размерности.Пусть дан массив
Деревом Фенвика будем называть массив из элементов: , где , как и в одномерном дереве Фенвика.
Содержание
Пример задачи для двумерного случая
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
- добавить точку в ;
- удалить точку из ;
- посчитать количество точек в прямоугольнике ;
Тогда дерево строится за , а запросы выполняются за
Добавляя точку вызовем
, а удаляя . Таким образом запрос дает количество точек в прямоугольнике.![](/wiki/images/thumb/4/4b/Example42.gif/600px-Example42.gif)
Псевдокод
int sum(x: int, y: int): int result = 0 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) for (int j = y; j >= 0; j = (j & (j + 1)) - 1) result += t[i][j]; return result;
func inc(x: int, y: int, delta: int): for (int i = x; i < maxX; i = (i | (i + 1))) for (int j = y; j < maxY; j = (j | (j + 1))) t[i][j] += delta;
Чтобы посчитать значение функции для прямоугольника включения-исключения. Например, для суммы:
Обобщение на большие размерности
Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.