81
правка
Изменения
вместо + некоторая абстрактная операция, осмысленные имена переменных
==Двумерное дерево отрезков==
{{Задача
|definition=
Дано поле размером <tex>N \times M</tex>, заполненное некоторыми числами. Необходимо уметь обрабатывать два типа запросов:
* Изменить некоторый элемент
* Посчитать сумму значение некоторой ассоциативной функции <tex>\times</tex> на прямоугольной области
}}
Двумерное дерево отрезков удобно хранить в виде массива, размером <tex>4N \times 4M</tex>. Каждая строчка такого массива соответствует некоторому отрезку по первой координате. Сама же строчка является деревом отрезков по второй координате.
На рисунке справа показан пример дерева отрезков для массива суммы на массиве 4 на 4, заполненного числами от 1 от 16. Например, в элементе <tex>a[2][0] = 100</tex> хранится сумма элементов, соответствующих отрезку <tex>[2..3]</tex> по первой координате и <tex>[0..3]</tex> по второй в исходном массиве. А в ячейке <tex>a[0][0] = 136</tex> хранится сумма всех элементов.
Интересно, что если построить дерево вначале по второй координате, а потом по первой, то получившийся массив будет таким же. Т. е. данный двумерный массив можно рассматривать как массив деревьев отрезков, где каждое дерево соответствует некоторому отрезку по второй координате, а в нем хранятся суммы по первой.
Заметим, что в общем случае для хранения <tex>p</tex>-мерного дерева отрезков требуется <tex>4^p n</tex> памяти, где <tex>n</tex> {{---}} общее количество элементов.
==Псевдокоддля двумерного случая==
Построение:
// first call - buildX(0, 0, n, a, t)
// a - исходный массив
// t - массив дерева отрезков
// [lxleftX, rxrightX) - полуинтервал
buildX(vxvertexX, lxleftX, rxrightX, a[][], t[][]) if lx leftX != rxrightX mx = (lx leftX + rx rightX + 1) / 2 buildX(vx vertexX * 2 + 1, lxleftX, mx, a, t) buildX(vx vertexX * 2 + 2, mx, rxrightX, a, t) buildY(vxvertexX, lxleftX, rxrightX, 0, 0, m, a, t)
buildY(vxvertexX, lxleftX, rxrightX, vyvertexY, lyleftY, ryrightY, a[][], t[][]) if ly leftY == ryrightY if lx leftX == rxrightX t[vxvertexX][vyvertexY] = a[lxleftX][lyleftY]
else
t[vxvertexX][vyvertexY] = t[vx vertexX * 2 + 1][vyvertexY] + <tex>\times</tex> t[vx vertexX * 2 + 2][vyvertexY]
else
my = (ly leftY + ry rightY + 1) / 2 buildY(vxvertexX, lxleftX, rxrightX, vy vertexY * 2 + 1, lyleftY, my, a, t) buildY(vxvertexX, lxleftX, rxrightX, vy vertexY * 2 + 2, my, ryrightY, a, t) t[vxvertexX][vyvertexY] = t[vxvertexX][vy vertexY * 2 + 1] + <tex>\times</tex> t[vxvertexX][vy vertexY * 2 + 2]
Подсчет суммы элементов:
// first call - sumX(0, 0, n - 1, lxleftX, rxrightX, lyleftY, ryrightY, t)
sumX(vxvertexX, tlxleftBorderX, trxrightBorderX, lxleftX, rxrightX, lyleftY, ryrightY, t[][]) if lx leftX > rxrightX
return 0
if lx leftX == tlx leftBorderX && rx rightX == trxrightBorderX return sumY(vxvertexX, 0, 0, m - 1, lyleftY, ryrightY) tmx = (tlx leftBorderX + trxrightBorderX) / 2 return sumX(vx vertexX * 2 + 1, tlxleftBorderX, tmx, lxleftX, min(rxrightX, tmx), lyleftY, ryrightY, t) +<tex>\times</tex> sumX(vx vertexX * 2 + 2, tmx + 1, trxrightBorderX, max(lxleftX, tmx + 1), rxrightX, lyleftY, ryrightY, t)
sumY(vxvertexX, vyvertexY, tlyleftBorderY, tryrightBorderY, lyleftY, ryrightY) if ly leftY > ryrightY
return 0
if ly leftY == tly leftBorderY && ry rightY == tryrightBorderY return t[vxvertexX][vyvertexY] tmy = (tly leftBorderY + tryrightBorderY) / 2 return sumY(vxvertexX, vy vertexY * 2 + 1, tlyleftBorderY, tmy, lyleftY, min(ryrightY, tmy), t) +<tex>\times</tex> sumY(vxvertexX, vy vertexY * 2 + 2, tmy + 1, tryrightBorderY, max(lyleftY, tmy + 1), ryrightY, t)
Обновление элемента:
// first call - updateX(0, 0, n - 1, x, y, val, t)
updateX(vxvertexX, lxleftX, rxrightX, x, y, val, t[][]) if lx leftX != rxrightX mx = (lx leftX + rxrightX) / 2
if x <= mx
updateX(vx vertexX * 2 + 1, lxleftX, mx, x, y, val, t)
else
updateX(vx vertexX * 2 + 2, mx + 1, rxrightX, x, y, val, t) updateY(vxvertexX, lxleftX, rxrightX, 0, 0, m - 1, x, y, val, t)
updateY(vxvertexX, lxleftX, rxrightX, vyvertexY, lyleftY, ryrightY, x, y, val, t[][]) if ly leftY == ryrightY if lx leftX == rxrightX t[vxvertexX][vyvertexY] = val
else
t[vxvertexX][vyvertexY] = t[vx vertexX * 2 + 1][vyvertexY] + <tex>\times</tex> t[vx vertexX * 2 + 2][vyvertexY]
else
my = (ly leftY + ryrightY) / 2
if y <= my
updateY(vxvertexX, lxleftX, rxrightX, vy vertexY * 2 + 1, lyleftY, my, x, y, val, t)
else
updateY(vxvertexX, lxleftX, rxrightX, vy vertexY * 2 + 2, my + 1, ryrightY, x, y, val, t) t[vxvertexX][vyvertexY] = t[vxvertexX][vy vertexY * 2 + 1] + <tex>\times</tex> t[vxvertexX][vy vertexY * 2 + 2]
