81
правка
Изменения
м
Нет описания правки
На рисунке справа показан пример дерева отрезков для массива 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> {{---}} общее количество элементов.
buildX(vx * 2 + 1, lx, mx, a, t)
buildX(vx * 2 + 2, mx, rx, a, t)
buildY(vx, lx, rx, 0, 0, m, a, t);
buildY(vx, lx, rx, vy, ly, ry, a[][], t[][])
t[vx][vy] = a[lx][ly]
else
t[vx][vy] = t[vx * 2 + 1][vy] + t[vx * 2 + 2][vy];
else
my = (ly + ry + 1) / 2
