Всем здравствуйте!
Недавно я старался написать двумерное дерево отрезков и попытался его использовать для перемножения матриц. Ничего похожего с помощью гугла не находится (_так что скорее всего все написанное ниже бред_), поэтому решил написать это в блог.
Пусть дана матрица 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
Меня интересует правильно ли я написал квадродерево (является ли то что я написал квадродеревом ?) и суммирование/обновление на прямоугольнике ? (считает вроде правильно, но возможно действия с деревом не за логарифм)
Ваш код я не читал, поэтому не знаю, что вы подразумеваете под квадродеревом. Но то, что обычно им называют, работает за , где N — количество клеток в дереве. То есть за линейное время от длины стороны, если высота и ширина равны. В таком случае приведенный алгоритм работает за куб, то есть не лучше трививльного.
Спасибо!
Если не ошибаюсь, у Вас групповое умножение и сложение элементов идут по разным индексам массива B. В операциях 1 и 3 дерево делает запрос вида [x][l..r], а в операции 2 — [l..r][x]. Так что ответ должен получаться неверный.
На двумерном дереве отрезков нельзя делать такие запросы ? Т. е. нельзя умножить прямоугольник [x][l..r] на константу, а потом запросить сумму на прямоугольнике [l..r][x] ?
Нет. Двумерное дерево отрезков может выполнять либо групповые операции, либо групповые запросы, но не вместе.
К слову, O(n^3) — давно уже не предел =) Одним из самых быстрых сейчас является алгоритм Вирджинии Вильямс (линк), хотя он актуален только на достаточно больших матрицах. А результатом применения теории групп, насколько я знаю, является возможность существования алгоритма с асимптотикой O(n^2). Может, сейчай уже что-то новое появилось — не знаю, давно не следил за сабжем.
Вообще, даже алгоритм Штрассена становится на современных компьютерах быстрее только с n порядка нескольких сотен, то есть когда время работы уже порядка десятых долей секунды. Потому что 8 умножений и 4 сложения размениваются на 7 умножений и как минимум 15 сложений, и константа получается очень большая.
А уж алгоритм Копперсмита-Винограда и подобные — это результаты ценные, но не практическими применениями.