Всем здравствуйте!
Недавно я старался написать двумерное дерево отрезков и попытался его использовать для перемножения матриц. Ничего похожего с помощью гугла не находится (_так что скорее всего все написанное ниже бред_), поэтому решил написать это в блог.
Пусть дана матрица An, x не содержащая нулевых элементов и матрица Bx, m. Нужно найти матрицу C = AB.
Алгоритм за O(n3):
For i := 1 to n
For j := 1 to x
For k := 1 to m
B[j][k] := B[j][k] * A[i][j] (1)
For k := 1 to m
For j := 1 to x
C[i][k] := C[i][k] + B[j][k] (2)
For j := 1 to x
For k := 1 to m
B[j][k] := B[j][k] * 1 / A[i][j] (3)
На каждой итерации цикла по i фиксируем i-ую строку матрицы A, i-ая строка матрицы C может быть получена как: .
Заранее посчитаем все произведения ai, j·Bj, k, а затем выполним только суммирование и вернем матрице B прежний вид, выполнив деление (это можно сделать так как A не содержит нулевых элементов).
Циклы (1) и (3) это операция умножения вектора на константу, а цикл (2) это операция нахождения суммы всех элементов вектора.
Следовательно, если построить двумерное дерево отрезков (или квадродерево) по матрице B, то можно выполнить эти операции быстрее, чем за n (n это max(n, x, m)).
Построение дерева выполняется за O(f(n)) < O(n3) операций, всего 1 раз. Умножение элементов прямоугольника на константу за O(f(n)) < O(n), всего 2x раз. Суммирование на прямоугольнике за O(f(n)) < O(n), всего m раз.
Пишу O(f(n)), т. к. не знаю точную асимптотику. Согласно http://e-maxx.ru/algo/segment_tree, http://habrahabr.ru/post/131072/ для двумерного дерева отрезков построение , суммирование и обновление . Для квадродерева, вроде(точно не знаю, хотелось бы узнать), построение , суммирование и обновление .
Получаем алгоритм за O(f(n)) < O(n3):
BuildTree(1, x, 1, m)
For i := 1 to n
For j := 1 to x
TreeUpdate(j, j, 1, m, A[i][j])
For k := 1 to m
C[i][k] := TreeSum(1, x, k, k)
For j := 1 to x
TreeUpdate(j, j, 1, m, 1.0 / A[i][j])
Если матрица An, x содержит нулевые элементы, найдем в ней минимальный элемент min Построим матрицу Dn, x из |min|, и тогда AB = (A + D)B - DB.
Вот код, в котором я попробовал все это реализовать: http://pastebin.com/iwHkYh9C
Меня интересует правильно ли я написал квадродерево (является ли то что я написал квадродеревом ?) и суммирование/обновление на прямоугольнике ? (считает вроде правильно, но возможно действия с деревом не за логарифм)