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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Многомерное [[дерево Фенвика]]''' - структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)
+
'''Многомерное [[дерево Фенвика]]''' (англ. <i> Multidimensional Binary Indexed Tree</i>) {{---}} структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)
 
# изменять значение любого элемента в k-мерном массиве;
 
# изменять значение любого элемента в k-мерном массиве;
 
# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на k-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.
 
# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на k-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.
 
}}
 
}}
 +
Рассмотрим для начала дерево Фенвика на примере k-мерного массива с <tex>k = 2</tex>, а затем посмотрим, как можно обобщить его на большие размерности.
  
 
Пусть дан массив <tex> A </tex> из <tex> n \times m </tex> элементов: <tex> a_{i,j}</tex>.<br/>
 
Пусть дан массив <tex> A </tex> из <tex> n \times m </tex> элементов: <tex> a_{i,j}</tex>.<br/>
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n \times m </tex> элементов: <tex> T_{i,j} = \sum\limits_{k = F(i)}^{i} \sum\limits_{q = F(j)}^{j}a_{k,q}</tex>, где <tex> F(i) = i \& (i + 1) </tex>.
+
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n \times m </tex> элементов: <tex> T_{i,j} = \sum\limits_{k = F(i)}^{i} \sum\limits_{q = F(j)}^{j}a_{k,q}</tex>, где <tex>F(i) = i\; \&\; (i + 1)</tex>, как и в одномерном [[дерево Фенвика|дереве Фенвика]].
  
 
==Пример задачи для двумерного случая==
 
==Пример задачи для двумерного случая==
[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейки, которые обновятся при изменении ячейки <tex>(5, 3)</tex>]]
 
 
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
 
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:
 
# добавить точку в <tex>(x, y)</tex>;
 
# добавить точку в <tex>(x, y)</tex>;
Строка 16: Строка 16:
 
# посчитать количество точек в прямоугольнике <tex>(0, 0), (x, y)</tex>;
 
# посчитать количество точек в прямоугольнике <tex>(0, 0), (x, y)</tex>;
  
<tex>n</tex> - количество точек, <tex>maxX</tex> - максимальная <tex>X</tex> координата, <tex>maxY</tex> - максимальная <tex>Y</tex> координата.<br/>
+
<tex>n</tex> {{---}} количество точек, <tex>maxX</tex> {{---}} максимальная <tex>X</tex> координата, <tex>maxY</tex> {{---}} максимальная <tex>Y</tex> координата.<br/>
 
Тогда дерево строится за <tex>O(n\cdot\log(maxX)\cdot\log(maxY))</tex>, а запросы выполняются за <tex>O(\log (maxX)\cdot\log (maxY))</tex>
 
Тогда дерево строится за <tex>O(n\cdot\log(maxX)\cdot\log(maxY))</tex>, а запросы выполняются за <tex>O(\log (maxX)\cdot\log (maxY))</tex>
  
Добавляя точку вызовем <tex>inc(x, y, 1)</tex>, а удаляя <tex>inc(x, y, -1)</tex>. Таким образом запрос <tex>sum(x, y)</tex> дает количество точек в прямоугольнике.
+
Добавляя точку вызовем <tex>\mathrm{inc}(x, y, 1)</tex>, а удаляя <tex>\mathrm{inc}(x, y, -1)</tex>. Таким образом запрос <tex>\mathrm{sum}(x, y)</tex> дает количество точек в прямоугольнике.
  
''Пример реализации для двумерного случая:''
+
[[Файл:example42.gif |thumb|600px|center|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены элементы, которые обновятся при изменении ячейки <tex>(5, 3)</tex>. Чтобы обновить элемент <tex>(X, Y)</tex>, по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее <tex>X</tex> и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под <tex>Y</tex>(в рамках обозначений данного рисунка).]]
  
<code>
+
==Псевдокод==
vector <vector <int> > t;
+
<tex>\mathtt{t}</tex> {{---}} массив, в котором хранится дерево Фенвика.
int n, m;
+
<code style = "display: inline-block;">
   
+
  '''int''' sum(x: '''int''', y: '''int'''):
int sum (int x, int y)
+
         '''int''' result = 0
{
+
         '''for''' ('''int''' i = x; i >= 0; i = (i & (i + 1)) - 1)
         int result = 0;
+
            '''for''' ('''int''' j = y; j >= 0; j = (j & (j + 1)) - 1)
         for (int i = x; i >= 0; i = (i & (i+1)) - 1)
+
              result += t[i][j];
          for (int j = y; j >= 0; j = (j & (j+1)) - 1)
+
         '''return''' result;
              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;
 
}
 
 
</code>
 
</code>
 +
<code style = "display: inline-block;">
 +
'''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;
 +
</code>
 +
 +
Чтобы посчитать значение функции для прямоугольника <tex>(x_1, y_1), (x_2, y_2)</tex> нужно воспользоваться формулой [[Формула включения-исключения|включения-исключения]]. Например, для суммы: <tex>s = \mathrm{sum}(x_2,y_2)-\mathrm{sum}(x_2,y_1 - 1)-\mathrm{sum}(x_1 - 1,y_2)+\mathrm{sum}(x_1 - 1,y_1 - 1)</tex><br/>
 +
[[Файл:ФормулаВключения-Исключения.jpg]]
 +
 +
====Обобщение на большие размерности====
 +
Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.
 +
 +
==См. также==
 +
* [[Дерево Фенвика]]
 +
* [[Встречное дерево Фенвика]]
 +
* [[Дерево Фенвика для некоммутативных операций]]
  
Чтобы посчитать значение функции для прямоугольника <tex>(x_1, y_1), (x_2, y_2)</tex> нужно воспользоваться формулой включения-исключения. Например для суммы: <tex>s = sum(x_2,y_2)-sum(x_2,y_1 - 1)-sum(x_1 - 1,y_2)+sum(x_1 - 1,y_1 - 1)</tex>
+
==Источники информации==
 +
*[https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ Topcoder {{---}} Binary Indexed Trees]
 +
*[http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
  
== Полезные ссылки: ==
+
[[Категория: Дискретная математика и алгоритмы]]
Wikipedia: [http://en.wikipedia.org/wiki/Fenwick_tree Fenwick tree] <br/>
+
[[Категория: Модификации структур данных]]
e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] <br/>
 
TopCoder:  [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find Binary Indexed Trees]
 

Текущая версия на 19:07, 4 сентября 2022

Определение:
Многомерное дерево Фенвика (англ. Multidimensional Binary Indexed Tree) — структура данных, требующая [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 - максимальное значение для каждой координаты.

Рассмотрим для начала дерево Фенвика на примере k-мерного массива с [math]k = 2[/math], а затем посмотрим, как можно обобщить его на большие размерности.

Пусть дан массив [math] A [/math] из [math] n \times m [/math] элементов: [math] a_{i,j}[/math].
Деревом Фенвика будем называть массив [math] T [/math] из [math] n \times m [/math] элементов: [math] T_{i,j} = \sum\limits_{k = F(i)}^{i} \sum\limits_{q = F(j)}^{j}a_{k,q}[/math], где [math]F(i) = i\; \&\; (i + 1)[/math], как и в одномерном дереве Фенвика.

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

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

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

[math]n[/math] — количество точек, [math]maxX[/math] — максимальная [math]X[/math] координата, [math]maxY[/math] — максимальная [math]Y[/math] координата.
Тогда дерево строится за [math]O(n\cdot\log(maxX)\cdot\log(maxY))[/math], а запросы выполняются за [math]O(\log (maxX)\cdot\log (maxY))[/math]

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

Пример дерева Фенвика [math](16 \times 8)[/math]. Синим обозначены элементы, которые обновятся при изменении ячейки [math](5, 3)[/math]. Чтобы обновить элемент [math](X, Y)[/math], по первой координате нам надо зайти во все столбцы(деревья по второй координате), находящиеся левее [math]X[/math] и на одной горизонтальной линии с ним, и в каждом из них обновить все ячейки под [math]Y[/math](в рамках обозначений данного рисунка).

Псевдокод

[math]\mathtt{t}[/math] — массив, в котором хранится дерево Фенвика.

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;

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

Обобщение на большие размерности

Дерево Фенвика относится к структурам данных, требующим малое количество дополнительной памяти. В комбинации с простым представлением тривиального случая данной структуры это дает возможность легко повышать размерность дерева Фенвика, в котором в ячейках какого-то фиксированного уровня будет находиться дерево меньшей размерности. Для его реализации нам достаточно во всех операциях для каждой новой размерности просто добавить вложенный цикл, пробегающий в ней соответствующие индексы.

См. также

Источники информации