sum += a[lo]
==

The query takes less than $k + n/k + k = 2k + n/k$ time. $2k + n/k$ is minimized when $k$ is $O(sqrt(n))$. For $k = sqrt(n)$ the query takes $O(sqrt(n))$ time.

The query takes less than $k + n/k + k = 2k + n/k$ time. $2k + n/k$ is minimized when $k$ is $O(sqrt(n))$. For $k = \sqrt(n)$ the query takes $O(\sqrt(n))$ time.

This trick also works for other associative operations, like: min, gcd, product etc.

bq. Given two strings A (n characters) and B (m characters), find their longest common subsequence. (eg. The longest common sub sequence for abcabc and abcbcca is abcbc.)

There is a standard dynamic programming solution which uses an array best[i][j] to mean the longest common sub sequence for A[0:i] and B[0:j], computed as below:

There is a standard dynamic programming solution which uses an array $best[i][j]$ to mean the longest common sub sequence for $A[0:i]$ and $B[0:j]$, computed as below:

== code(c) |
if A[i] == B[j]:

  best[i][j] = max(best[i-1][j], best[i][j-1])
==

This algorithm takes O(nm) time and only O(n) space, since to compute a row you just need the previous row.
If you must return the actual sub sequence this doesn't work. You can keep an array of parent pointers, so that for each state (i, j) you know the previous state in the solution. The longest sub sequence corresponds to a path from (n-1, m-1) to (0, 0) on the parent matrix.  This solution takes O(nm) space.

This algorithm takes $O(nm)$ time and only $O(n)$ space, since to compute a row you just need the previous row.
If you must return the actual sub sequence this doesn't work. You can keep an array of parent pointers, so that for each state $(i, j)$ you know the previous state in the solution. The longest sub sequence corresponds to a path from $(n-1, m-1)$ to $(0, 0)$ on the parent matrix.  This solution takes $O(nm)$ space.

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;}blog/square-root-trick?image02.png 90%!

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

We can start from the last saved row to compute the solution path from the $[n/k] * k$th row to the $n - 1%th. Then we go downwards to compute the part of the solution between the $ik$th row and the $(i+1)k$th row. Computing part of the path between row $ik$ and row $(i+1)k$ takes $O(km)$ space and $O(km)$ time. Computing the whole path takes $O(n/k (km)) = O(nm)$ time and $O(km)$ space. Keeping every $k$th row in memory takes $O([n/k]m)$ memory. Again we minimize memory usage by using $k = \sqrt n$

h2. Caveats