Being flexible and easy to code, the square root trick is pretty popular in the Romanian programming contests community. It even has a name: "jmenul lu Batog" which means Batog's trick :). Bogdan Batog introduced it to a few high school students more than ten years ago and the trick entered romanian coding contest folklore.

The idea is that we can use bucketing or a two level tree as some people call it to improve naive data structures or algorithms. The square root part appears when we minimize the function n/x + x, we'll see more about that later on.

The idea is that we can use bucketing or a two level tree as some people call it to improve naive data structures or algorithms. The square root part appears when we minimize the function $n/x + x$, we'll see more about that later on.

Let’s check out a few problems that explain how the trick works.
h2. Range Sum
bq.. Given A, an n elements array, implement a data structure for point updates and range sum queries:

- set(i, x): A[i] := x,
- sum(lo, hi) returns A[lo] + A[lo+1] + .. + A[hi].

- update(i, x): A[i] := x,
- query(lo, hi) returns A[lo] + A[lo+1] + .. + A[hi].

p. The naive solution uses an array. It takes $O(1)$ time for an update and $O(hi - lo) = O(n)$ for the range sum.

A more efficient solution splits the array into length $k$ slices and stores the slice sums in an array $S$.

p. 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, because we have to update the value for A and the value for the corresponding $S$.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!

p. The update takes constant time, because we have to update the value for A and the value for the corresponding $S$.
The query is interesting. The elements of the first and last slice (partially contained in the queried range) have to be traversed one by one, but for slices completely contained in our range we can use the values in $S$ directly and get a performance boost.
 
p. Here is an update example:
!{margin-right: 20px; auto;display:block;}blog/square-root-trick?image01.png!
 
p. In $update(6, 5)$ we have to change $A[6]$ to 5 which results in changing the value of $S[1]$ to keep $S$ up to date.
 
!{margin-right: 20px; auto;display:block;}blog/square-root-trick?image00.png!
 
In $query(2, 14)$ we get
== code(c) |
query(2, 14) = A[2] + A[3]+
               (A[4] + A[5] + A[6] + A[7]) +
               (A[8] + A[9] + A[10] + A[11]) +
               A[12] + A[13] + A[14]
             = A[2] + A[3] +
               S[1] + S[2] +
               A[12] + A[13] + A[14]
             = 0 + 7 + 11 + 9 + 5 + 2 + 0
             = 34
==
Here's how the code looks:

The code looks like this:

== code(c) |
def update(S, A, i, k, x):
  S[i/k] = S[i/k] - A[i] + x
  A[i] = x

==
 
The 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;}blog/square-root-trick?image00.png!
 
The code looks like this:
== code(c) |

def query(S, A, lo, hi, k):
  s = 0
  i = lo

  return s
==

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.

Each query takes on average $k/2 + n/k + k/2 = k + n/k$ time. This is minimized for $k = sqrt(n)$. So we get a $O(sqrt(n))$ time complexity query.

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

public

protected