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.

Enough introduction, let’s check out a few problems!

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. Let’s check out a few problems that explain how the trick works.

h2. Range Sum

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.

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!
The code looks like this: