When to Use Sqrt Decomposition

Use sqrt decomposition when:

$1.$ You need a quick implementation with reasonable complexity

$2.$ The problem has mixed operations where $O(\sqrt{n})$ is acceptable

$3.$ Segment trees feel like overkill or you're unsure how to adapt them Avoid sqrt decomposition when:

$1.$ You need $O(\log n)$ per operation for tight time limits

$2.$ The problem has nested structures (use segment tree of segment trees)

$3.$ You need persistent data structures The technique is a solid fallback. Not the fastest, but reliably correct.