Всем здравствуйте!

Недавно я старался написать двумерное дерево отрезков и попытался его использовать для перемножения матриц. Ничего похожего с помощью гугла не находится (_так что скорее всего все написанное ниже бред_), поэтому решил написать это в блог.

Пусть дана матрица A_n, x не содержащая нулевых элементов и матрица B_x, m. Нужно найти матрицу C = AB.

Алгоритм за O(n³):

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 может быть получена как: .

Заранее посчитаем все произведения a_i, j·B_j, k, а затем выполним только суммирование и вернем матрице B прежний вид, выполнив деление (это можно сделать так как A не содержит нулевых элементов).

Циклы (1) и (3) это операция умножения вектора на константу, а цикл (2) это операция нахождения суммы всех элементов вектора.

Следовательно, если построить двумерное дерево отрезков (или квадродерево) по матрице B, то можно выполнить эти операции быстрее, чем за n (n это max(n, x, m)).

Построение дерева выполняется за O(f(n)) < O(n³) операций, всего 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(n³):

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])

Если матрица A_n, x содержит нулевые элементы, найдем в ней минимальный элемент min Построим матрицу D_n, x из |min|, и тогда AB = (A + D)B - DB.

Вот код, в котором я попробовал все это реализовать: http://pastebin.com/iwHkYh9C

Меня интересует правильно ли я написал квадродерево (является ли то что я написал квадродеревом ?) и суммирование/обновление на прямоугольнике ? (считает вроде правильно, но возможно действия с деревом не за логарифм)