Изменения

# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на k-мерном прямоугольнике <tex> [i_1, \ldots ,i_k] </tex>;<br/> где n - максимальное значение для каждой координаты.

}}

Пусть дан массив <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>(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/>

[[Файл:ФормулаВключения-Исключения.jpg]]

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