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.