Range Sum BIT Solution

Implement the Fenwick Tree solution for range sum queries.

Differences from segment tree:

• Less code (~20 lines vs ~50)
• $n$ space vs $4n$
• Only prefix queries directly; range requires subtraction
• Typically faster in practice due to simpler operations

When to choose BIT over segment tree:

• You only need prefix/range queries (not arbitrary operations)
• The operation is invertible (sum: subtract; but min: not invertible)
• You want simpler, faster code

When to choose segment tree:

• Range updates needed (lazy propagation)
• Non-invertible operations (min, max, GCD)
• More complex queries (k-th element, etc.)

Time: $O(\log n)$. Space: $O(n)$.