# Updating maximum sum subrectangle in a sparse matrix when one element is changed

I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional Kadane's 2-d algorithm of O(m^2 n) for sufficiently sparse matrices. The sparse matrix algorithm, which is also O(m^2 n) time for dense matrices, matching Kadane's algorithm, can be found here https://stackoverflow.com/questions/17558028/maximum-sum-subrectangle-in-a-sparse-matrix .Now I want to know if the optimal solution can be updated quickly if one entry in the matrix is changed. By "quickly" I mean something like O(m log n) time or better. It's possible that perhaps the matrix does not have to be sparse to work out a solution, however a solution when N = O(min(m,n)) would be ok. Preprocessing is also ok as long as the amortized cost of preprocessing time per element changed matches or beats something like O(m log n) time for m changes.

• To make the question self-contained and help us help you, would you be able to provide a description or summary of Kadane's 2-d algorithm or a link to a description of it?
– D.W.
Jan 21, 2014 at 18:01
• @D.W. thanks, link to the existing algorithm is now given. Jan 21, 2014 at 19:54
• Thanks, that's interesting reading. It still doesn't seem to offer a description of Kadane's algorithm, though. Do you have a reference for Kadane's algorithm? Perhaps you might want to add the main ideas of Kadane's algorithm to the question to make your question self-contained.
– D.W.
Jan 21, 2014 at 20:21

The algorithm given at your link builds a one-dimensional array A[] for each i,j (where $1\le i \le j \le m$), where A[k] = sum{B[i..j,k]}. So, let's keep a copy of each of those arrays. That can be done by using a persistent data structure for the array, say, a persistent balanced binary tree. In this way, the output of the algorithm shown there is $m(m-1)/2$ 1-D arrays, one for each i,j.
Now let's say that the entry B[i*,k] gets modified in the matrix B. Obviously, this affects the entry A[k] in each of the arrays for i,j, where i <= i* <= j. That's at most $O(m^2)$ of the 1-D arrays. And, we can go update that one entry of those arrays in $O(m^2)$ time. In fact, for a sparse matrix, the running time is even less: it is something like the square of the number of non-zero entries in the k-th column of the matrix B.