Многомерное дерево Фенвика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример задачи для двумерного случая)
(Пример задачи для двумерного случая)
Строка 8: Строка 8:
  
 
==Пример задачи для двумерного случая==
 
==Пример задачи для двумерного случая==
 +
[[Файл:example42.gif |thumb|600px|right |Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейки, которые обновятся при изменении ячейки <tex>(5, 3)</tex>]]
 
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
 
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
 
# добавить точку в <tex>(x, y)</tex>;
 
# добавить точку в <tex>(x, y)</tex>;
Строка 41: Строка 42:
 
</code>
 
</code>
  
[[Файл:example42.gif]] <br/>
+
Чтобы посчитать значение функции для прямоугольника <tex>(x_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(x_1,y_1)</tex>
Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейки, которые обновятся при изменении ячейки <tex>(5, 3)</tex>
 
  
 
== Полезные ссылки: ==
 
== Полезные ссылки: ==

Версия 22:52, 7 июня 2011

Определение:
Многомерное дерево Фенвика - структура данных, требующая [math] O(n^k) [/math] памяти и позволяющая эффективно (за [math] O(\log^k n) [/math])
  1. изменять значение любого элемента в k-мерном массиве;
  2. выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] G [/math] на k-мерном прямоугольнике [math] [i_1, \ldots ,i_k] [/math];
    где n - максимальное значение для каждой координаты.


Пример задачи для двумерного случая

Пример дерева Фенвика [math](16 \times 8)[/math]. Синим обозначены ячейки, которые обновятся при изменении ячейки [math](5, 3)[/math]

Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:

  1. добавить точку в [math](x, y)[/math];
  2. удалить точку из [math](x, y)[/math];
  3. посчитать количество точек в прямоугольнике [math](0, 0), (x, y)[/math];

m - количество точек, maxX - максимальная x координата, maxY - максимальная y координата. тогда дерево строится за [math]O(m\log (maxX)\,\log (maxY))[/math], а запросы выполняются за [math]O(\log (maxX)\log (maxY))[/math]

Добавляя точку вызовем [math]inc(x, y, 1)[/math], а удаляя [math]inc(x, y, -1)[/math]. Таким образом запрос [math]sum(x, y)[/math] дает количество точек в прямоугольнике.

Пример реализации для двумерного случая:

vector <vector <int> > t;
int n, m;

int sum (int x, int y)
{
       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;
}

void inc (int x, int y, int delta)
{
       for (int i = x; i < n; i = (i | (i+1)))
          for (int j = y; j < m; j = (j | (j+1)))
             t[i][j] += delta;
}

Чтобы посчитать значение функции для прямоугольника [math](x_1, y_1), (x_2, y_2)[/math] нужно воспользоваться формулой включения-исключения. Например для суммы: [math]s = sum(x_2,y_2)-sum(x_2,y_1)-sum(x_1,y_2)+sum(x_1,y_1)[/math]

Полезные ссылки:

Wikipedia: Fenwick tree
e-maxx.ru: Дерево Фенвика
TopCoder: Binary Indexed Trees