Обновление максимального прямоугольника суммы в разреженной матрице при изменении одного элемента
У меня есть матрица mxn, которая редка с N ненулевых записей.
Модифицированная версия Kadane's 2-d algorithm можно найти максимальную сумму под прямоугольника в O(m N log n) время, которое бьет традиционный алгоритм Кадане O(m^2 n) для достаточно разреженных матриц.
Теперь я хочу знать, можно ли быстро обновить оптимальное решение, если одна запись в матрице будет изменена.
Под "быстро" я имею в виду что-то вроде O(m log n) time or better,
Вполне возможно, что, возможно, матрица не должна быть разреженной, чтобы выработать a solution, however a solution when N = O(min(m,n)) would be ok,