Блог пользователя Snef

Автор Snef, 12 лет назад, По-русски

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

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

Пусть дана матрица 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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится