Section Recap

You now understand Fenwick Trees: Core Operations:

• Build: $O(n)$ or $O(n \log n)$
• Point update: $O(\log n)$
• Prefix query: $O(\log n)$

Techniques:

• lowbit: i & (-i) extracts lowest set bit
• Query: subtract lowbit repeatedly
• Update: add lowbit repeatedly
• Range query: $\text{prefix}(r) - \text{prefix}(l-1)$

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.