| Structure | Preprocess | Query | Update | Space | |-----------|------------|-------|--------|-------| | Sparse Table | | | N/A | | | Segment Tree | | | | | | BIT | | | | | Use Sparse Table when:
- Array is static (no updates)
- Many queries (the query pays off)
- Operation is idempotent (min, max, gcd, AND, OR)
Use Segment Tree when:
- Updates are needed
- Non-idempotent operations
- More complex queries
Use BIT when:
- Only need prefix/range sums
- Want simpler code than segment tree