You now understand Fenwick Trees: Core Operations:
- Build: or
- Point update:
- Prefix query:
Techniques:
- lowbit:
i & (-i)extracts lowest set bit - Query: subtract lowbit repeatedly
- Update: add lowbit repeatedly
- Range query:
Extensions:
- Range update + point query: use difference array
- Range update + range query: use two BITs
- 2D BIT: nest the 1D operations
- Order statistics: binary search on prefix sums
When to Use:
- Point updates + prefix/range queries
- Invertible operations (sum, XOR)
- Want simpler code than segment tree
Fenwick Trees are a competitive programmer's best friend for range sum problems. The code is short, fast, and hard to mess up.