| 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
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
$ curl repovive.com/roadmaps/data-structures/fenwick-trees/bit-vs-segment-tree
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████