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.
h2. Nearest neighbour

bq. Given a set S of n points and a query point p, find the point in S closest to p.

bq. Given a set $S$ of $n$ points and a query point $p$, find the point in $S$ closest to $p$.

For uniformly distributed points, a good strategy is to represent the space as a grid and maintain a list of inner points for each cell. For a given query point, we can check the cell the point falls into and its neighbouring cells. For a sqrt(n) * sqrt(n) grid we’ll have one point per cell, on average. So, on average, finding the point in S closest to p, requires traversing a constant number of cells.

For uniformly distributed points, a good strategy is to represent the space as a grid and maintain a list of inner points for each cell. For a given query point, we can check the cell the point falls into and its neighbouring cells. For a $\sqrt{n} * \sqrt{n}$ grid we’ll have one point per cell, on average. So, on average, finding the point in $S$ closest to $p$, requires traversing a constant number of cells.

h2. Longest common subsequence solution

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 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$

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

The above problems have better solutions using interval trees or some other clever tricks. The sqrt trick is nice, since it improves the naive solution a lot without much effort.

The above problems have better solutions using interval trees or some other clever tricks. The square root trick is nice, since it improves the naive solution a lot without much effort.

h2. Additional problems

# *Josephus problem* n people numbered from 1 to n sit in a circle and play a game. Starting from the first person and every kth person is eliminated. Write an algorithm that prints out the order in which people are eliminated.
# *(Level ancestor)* You are given an tree of size n. ancestor(node, levelsUp) finds the node’s ancestor that is levelsUp steps up. For example, ancestor(node, 1) returns the father and ancestor(node, 2) returns the grandfather. Implement ancestor(node, levelsUp) efficiently. (O(sqrt(n)) per query)
# *(Range median)* You are given an array of size n. Implement a data structure to perform update operations a[i] = k and range median operations efficiently. The range median query, median(l, r)  returns the median element of the sorted subsequence a[l..r]. ($O(\log n)$ per update and O(sqrt n log n) per query)

# *Josephus problem* $n$ people numbered from 1 to $n$ sit in a circle and play a game. Starting from the first person and every $k$th person is eliminated. Write an algorithm that prints out the order in which people are eliminated.
# *(Level ancestor)* You are given an tree of size $n$. $ancestor(node, levelsUp)$ finds the node’s ancestor that is $levelsUp$ steps up. For example, $ancestor(node, 1)$ returns the father and ancestor(node, 2) returns the grandfather. Implement $ancestor(node, levelsUp)$ efficiently. ($O(sqrt{n})$ per query)
# *(Range median)* You are given an array of size $n$. Implement a data structure to perform update operations $a[i] = k$ and range median operations efficiently. The range median query, $median(l, r)$  returns the median element of the sorted subsequence $a[l..r]$. ($O(\log{n})$ per update and $O(\sqrt{n}\log{n})$ per query)

You can discuss the problems in the comments section.