BIT vs Segment Tree

| Feature | BIT | Segment Tree | |---------|-----|--------------| | Space | $n$ | $4n$ | | Code length | ~10 lines | ~50 lines | | Constant factor | Lower | Higher | | Point update | $O(\log n)$ | $O(\log n)$ | | Prefix query | $O(\log n)$ | $O(\log n)$ | | 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