CONCEPT · Candidate Master
Fenwick tree
also BIT · binary indexed tree
Point add and prefix sum in O(log n) via lowest-set-bit jumps. Range sum is two prefixes. Needs an invertible combine.
Intuition
Each index owns a small prefix ending at itself. i & -i is the length of that prefix.
When to reach for it
- Dynamic range sums / XORs
- Inversion counts (add frequencies)
- Subtree sums after an Euler tour
- CSES Dynamic Range Sum Queries
Usual pits
- 0-based index 0 infinite-loops — use 1-based
- Min/gcd are not invertible — use a segment tree
- Point set ≠ point add; store the raw array
- Negative prefix subtraction without +mod