Why it matters

When you need prefix sums with updates, Fenwick tree is 2x faster and half the code of segment tree. Understanding the trade-off matters.

Advertisement

The architecture

Structure: array indexed 1 to n. Position i stores sum of a specific range determined by i's low bit.

Update(i, val): i += lowbit(i) walk, adding val to each visited position. O(log n).

Prefix sum(i): i -= lowbit(i) walk, summing visited positions. O(log n).

Fenwick tree navigationLowbit tricki & (-i)Update walkadd + climbQuery walksum + descendRange sum [l, r] = prefix(r) - prefix(l-1); update range needs difference array trick
Fenwick tree operations.
Advertisement

How it works end to end

Range sum: prefix(r) - prefix(l-1). Simple but requires operation to be invertible (sum, XOR — yes; min, max — no).

Range update, point query: apply update on difference array (add val at l, subtract at r+1). Query becomes prefix sum.

2D Fenwick: extends to grids. O(log² n) per operation.