Binary Indexed Trees (BIT/Fenwick Trees) also support range queries and updates.
When to use each? Use BIT when:
- Only need prefix queries (sum from 0 to i)
- Need simpler, faster implementation
- Memory is tight (BIT uses exactly space)
- Operation is invertible (sum, XOR, but not min/max)
Use Segment Tree when:
- Need arbitrary range queries (not prefix)
- Need range updates with lazy propagation
- Operation is not invertible (min, max, GCD)
- Need more complex query types (count, frequency)
BIT is 2-3x faster in practice for prefix queries.
But segment trees are more versatile. Learn both. Use BIT when you can, segment tree when you must.