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 $$$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




