A more efficient solution splits the array into length k slices and stores the slice sums in an array S.
The update takes constant time.

!<{margin-right: 20px; auto;display:block;border: 1px solid gray;}blog/square-root-trick?image01.png!

!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!

The code looks like this:
== code(c) |

The range sum query is interesting. Slices completely contained in our range are summed up fast. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one.

!<{margin-right: 20px; auto;display:block;border: 1px solid gray;}blog/square-root-trick?image00.png!

!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!

The code looks like this:
== code(c) |

Let's see how can we use less memory.
We solve the problem once and save every kth row from the best matrix and from the parent matrix.

!<{margin-right: 20px; auto;display:block;border: 1px solid gray;}blog/square-root-trick?image02.png 60%!

!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image02.png 60%!

We can start from the last saved row to n to compute the solution path from the n - 1 line to [n/k] * k line. And then go lower and lower to compute the part of the solution between the ik (i+1)k. Computing part of the path between row ik and row (i+1)k takes k * m space and k * m time. Computing the whole path takes n/k * (k * m) = nm time and km space, keeping every kth row in memory takes [n/k]m. again we minimize memory by using k = sqrt n
Caveats