| Feature | BIT | Segment Tree | |---------|-----|--------------| | Space | | | | Code length | ~10 lines | ~50 lines | | Constant factor | Lower | Higher | | Point update | | | | Prefix query | | | | Range query | Via subtraction | Direct | | Range update | Two BITs | Lazy propagation | | Min/Max query | No | Yes | | Order statistics | Yes (with tricks) | Yes | Use BIT when:
- You only need prefix/range sum (or XOR, or similar invertible operation)
- You want simple, fast code
Use Segment Tree when:
- You need range updates with lazy propagation
- You need non-invertible operations (min, max, GCD)
- You need more complex queries