Updating maximum sum subrectangle in a sparse matrix when one element is changed
Yes, absolutely.  There is a straightforward way to do what you want, if you work through the details of the algorithm given at the link in your question.  The trick is to use persistent data structures, to avoid re-computing data multiple times.

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 &lt;= i* &lt;= 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.