http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=SphilippovВикиконспекты - Вклад участника [ru]2026-05-19T14:16:45ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0&diff=26430Многомерное дерево Фенвика2012-06-21T20:58:56Z<p>Sphilippov: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Многомерное [[дерево Фенвика]]''' - структура данных, требующая <tex> O(n^k) </tex> памяти и позволяющая эффективно (за <tex> O(\log^k n) </tex>)<br />
# изменять значение любого элемента в k-мерном массиве;<br />
# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на k-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.<br />
}}<br />
Рассмотрим дерево Фенвика на примере k-мерного массива с k = 2, с увеличением k на единицу в операциях будет просто добавляться проход по k+1 измерению. <br />
<br />
Пусть дан массив <tex> A </tex> из <tex> n \times m </tex> элементов: <tex> a_{i,j}</tex>.<br/><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>, как и в одномерном [[дерево Фенвика|дереве Фенвика]].<br />
<br />
==Пример задачи для двумерного случая==<br />
[[Файл:example42.gif |thumb|600px|right|Пример дерева Фенвика <tex>(16 \times 8)</tex>. Синим обозначены ячейки, которые обновятся при изменении ячейки <tex>(5, 3)</tex>]]<br />
Пусть имеем набор точек на плоскости с неотрицательными координатами. Определены 3 операции:<br />
# добавить точку в <tex>(x, y)</tex>;<br />
# удалить точку из <tex>(x, y)</tex>;<br />
# посчитать количество точек в прямоугольнике <tex>(0, 0), (x, y)</tex>;<br />
<br />
<tex>n</tex> - количество точек, <tex>maxX</tex> - максимальная <tex>X</tex> координата, <tex>maxY</tex> - максимальная <tex>Y</tex> координата.<br/><br />
Тогда дерево строится за <tex>O(n\cdot\log(maxX)\cdot\log(maxY))</tex>, а запросы выполняются за <tex>O(\log (maxX)\cdot\log (maxY))</tex><br />
<br />
Добавляя точку вызовем <tex>inc(x, y, 1)</tex>, а удаляя <tex>inc(x, y, -1)</tex>. Таким образом запрос <tex>sum(x, y)</tex> дает количество точек в прямоугольнике.<br />
<br />
''Пример реализации для двумерного случая:''<br />
<br />
<code><br />
vector <vector <int> > t;<br />
int n, m;<br />
<br />
int sum (int x, int y)<br />
{<br />
int result = 0;<br />
for (int i = x; i >= 0; i = (i & (i+1)) - 1)<br />
for (int j = y; j >= 0; j = (j & (j+1)) - 1)<br />
result += t[i][j];<br />
return result;<br />
}<br />
<br />
void inc (int x, int y, int delta)<br />
{<br />
for (int i = x; i < n; i = (i | (i+1)))<br />
for (int j = y; j < m; j = (j | (j+1)))<br />
t[i][j] += delta;<br />
}<br />
</code><br />
<br />
Чтобы посчитать значение функции для прямоугольника <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><br/><br />
[[Файл:ФормулаВключения-Исключения.jpg]]<br />
<br />
<br />
== Полезные ссылки: ==<br />
Wikipedia: [http://en.wikipedia.org/wiki/Fenwick_tree Fenwick tree] <br/><br />
e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] <br/><br />
TopCoder: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find Binary Indexed Trees]</div>Sphilippov