SQRT decomposition, slightly faster
Difference between en5 and en6, changed 0 character(s)
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? Although it is not a huge complexity improvement, a $1.5\times$ difference can often be the difference between AC and TLE if you make sketchy square root complexity solutions, so I think it is still worth sharing.↵
↵
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.↵
↵
![ ](/predownloaded/f2/79/f279be65e9438d30059072b478b9265f0e3a365b.png)↵
↵
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:↵
↵
![ ](/predownloaded/c4/78/c478a4acd641d73150e95144daf4febd1f32a2cf.png)↵
↵
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}$:↵
↵
![ ](/predownloaded/87/2d/872d32d9a40b6072ece5acc2a97ee0e2bc079e72.png)↵
↵
The amount of work done for queries is at most $2\sqrt{gn}$ instead of $3\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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English BLOBVISGOD 2026-11-13 20:55:33 0 (published)
en5 English BLOBVISGOD 2026-11-13 20:55:04 214
en4 English BLOBVISGOD 2026-11-13 20:51:33 85
en3 English BLOBVISGOD 2026-11-13 20:47:59 990
en2 English BLOBVISGOD 2026-11-13 20:36:32 355
en1 English BLOBVISGOD 2026-11-13 20:08:17 1169 Initial revision (saved to drafts)