The beauty of SQRT(N)

Many quadratic algorithms can be "changed" into a linear version pre-processing sqrt(N) "points" so that the algorithm will be a linear one on the subset of selected "points". This is a typical trick adopted in clustering and in many other situations. Let's review some examples.

RMQ

Range minumum queries is the problem of finding the minimum value into an interval. A trivial solution is quadratic and can be computed with dynamic programming, by observing that the minimum for an interval with 1 number is the same number and that we can get the minimum for the interval [i, j] if we know where is the index corresponding to the minimum for the interval [i, j-1].

We can use the above trick and divide the interval in SQRT(N) intervals and for each of them precompute the minimum in O(N), then we can answer the query in SQRT(N) just by checking the overlapping intervals with the query -- those are no more than SQRT(N). So we will have