Intro

Segment trees are powerful but verbose. For many problems, you only need prefix queries (sum of elements $0$ to $i$), not arbitrary range queries.

Fenwick Trees (also called Binary Indexed Trees or BITs) provide:

• $O(\log n)$ prefix sum queries
• $O(\log n)$ point updates
• Only $n$ extra space (not $4n$ like segment trees)
• About 10 lines of code The tradeoff: Fenwick Trees directly support only prefix queries.

For range $[l, r]$, compute $\text{prefix}(r) - \text{prefix}(l-1)$. For range minimum queries, Fenwick Trees don't work directly. In this section, I'll teach you how Fenwick Trees use bit manipulation to achieve logarithmic operations, and when to choose them over segment trees.