Sparse Table vs Others

| Structure | Preprocess | Query | Update | Space | |-----------|------------|-------|--------|-------| | Sparse Table | $O(n \log n)$ | $O(1)$ | N/A | $O(n \log n)$ | | Segment Tree | $O(n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ | | BIT | $O(n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ | Use Sparse Table when:

• Array is static (no updates)
• Many queries (the $O(1)$ 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