Comparing Sqrt to Other Structures

Here's a decision guide: Use Segment Tree when:

• You need $O(\log n)$ per operation
• The operation is associative (sum, min, max, gcd)
• You need point or range updates with point or range queries

Use Sqrt Decomposition when:

• $O(\sqrt{n})$ is acceptable
• You want simpler code
• The problem doesn't fit segment tree structure well

Use MO's Algorithm when:

• Queries are offline (all known in advance)
• You can efficiently extend/shrink the range by one element
• Segment trees can't handle the query type