Here's a decision guide: Use Segment Tree when:
- You need 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:
- 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