We have all at some point tried to cheese a problem with square root decomposition, only to be met with a TLE verdict. What if I told you that it is possible to make your solution up to $$$1.5$$$ times faster, while barely changing anything?
Let us first look at where the cost of a query of regular square root decomposition comes from. A query can be split up into two parts: the $$$\sqrt{n}$$$-sized blocks that lie fully within the queried interval, and the single elements at the ends of the interval that are not part of any such block. We will for now assume that the cost of traversing a block and the cost of handling a single element at the ends is approximately the same, and then account for this difference later.

There can be almost $$$\sqrt{n}$$$ large blocks to handle, and simultaneously there can be almost $$$\sqrt{n}$$$ single elements to handle at both ends of the queried interval. Thus, in total this costs us $$$\sim3\sqrt{n}$$$ work. We can make this less, by making the blocks smaller, the closer they are to the begin or end of the array:

Since $$$2 \cdot \left(1+2+3+\ldots+\sqrt{n}\right) \approx n$$$, this comes down to having blocks of sizes $$$1,2,3,\ldots$$$ from the ends of the array, inwarwards. In the figure above, we see that if a query goes over the middle of the array, it requires less than $$$2\sqrt{n}$$$ work in total. Similarly, if a query does not go over the middle, $$$2\sqrt{n}$$$ work is required to answer the query. Now let us suppose that handling a block costs $$$g$$$ times more work than handling the single elements at the ends of the query interval. This can for example be the case if you do binary search in the blocks, in which case $$$g \sim \log(n)$$$. Then it turns out that the best size to choose for the $$$i$$$-th block on the left side of the array is approximately $$$gi$$$. In total, there are $$$\sim 2\sqrt{\frac{n}{g}}$$$ blocks, and the middle block has size $$$\sim \sqrt{gn}$$$:

Hence, choosing block sizes this way results in $$$1.5$$$ times faster queries, even in the unbalanced case. Lastly, I want to mention that updates are just as fast as when using the "regular" square root decomposition: The largest block, which is in the middle of the array, has exactly the same size in this new square root decomposition.



