1Understand
The idea
When an array changes and you also need range sums (or minimums), precompute partial answers over blocks whose sizes are powers of two. Both an update and a range query touch only O(log n) blocks. A Fenwick tree does this for sums in a few lines; a segment tree handles any associative operation.
Intuition
When an array changes and you also need range aggregates, precompute partial answers over blocks whose sizes are powers of two. Both an update and a range query touch O(log n) blocks.
A Fenwick (BIT) handles prefix sums with very little code; a segment tree supports any associative operation (sum, min, gcd) and easy range updates with lazy propagation.
Prefer these over rebuilding a prefix array when the problem mixes updates and queries.
What you will be able to do
- Implement a Fenwick tree
- Map values to ranks (coordinate compression)
When to use it
- Range sum / min with updates in between
- Count smaller elements after self
- Many queries on a changing array
2See it
Walkthrough
Fenwick range sum
a = [1, 3, 5, 7] (1-indexed BIT), prefix walks along lowbit.
1 / 4
BIT[i] stores sum of a responsible range ending at i. Build by point-add each value.
Live template
Line 1 active
Complexity: time O(log n) per op, space O(n)
Build O(n), query/update O(log n). Recomputing sums each time is O(n) per query. Prefix arrays are O(1) query but O(n) update, wrong when both operations appear. Fenwick is less flexible than a segment tree but faster to implement for sums.
Read the walkthrough as text
Fenwick range sum. Array [1,3,5,7] (1-indexed tree).
- Build by updating each position's value into the BIT.
- Prefix sum to index 3: walk index
3 → 2 → 0, summing nodes, gets1+3+5=9. - Range sum
[2,4]= prefix(4), prefix(1). - Point update index 2 by
+2: add 2 along2 → 4 → ....
Segment tree stores a full binary tree over the array; query splits the range into O(log n) nodes.
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Range sum with point updates
Example. Sum on [l,r] with updates between queries.
How. Fenwick tree on prefix sums; range sum = query(r)−query(l−1).
Range minimum / maximum
Example. Segment tree for min on range with updates.
How. Build tree; query merges min children; point update rewrites leaf upward.
Count inversions / smaller after self
Example. Reverse pairs count.
How. Fenwick on compressed ranks while scanning right to left.
Coordinate compression
Example. Map large values to 0..k−1 for Fenwick.
How. Sort unique values; rank[i] = index in sorted list.
Lazy propagation for range updates
Example. Add v to entire segment [l,r].
How. Segment tree with lazy tag push down on query/update path.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
1-indexing
Why it happens. Array is 0-indexed so Fenwick should match.
How it fails. update(0, x) without i+=1, updates index 0 in tree which is unused slot.
Fix. Internally use i+1 for user index i in update/query loops.
Static prefix sums
Why it happens. Rebuild prefix array after each update is still O(n) per query total.
How it fails. q updates each rebuild prefix, O(nq) instead of O(q log n).
Fix. Point update Fenwick in O(log n); range sum from two queries.
Update vs set
Why it happens. add(idx, newVal) feels like setting cell to newVal.
How it fails. Set nums[i]=5 from old 3 with add(i,5), tree has 8 at i instead of 5.
Fix. Point set: add(i, newVal - oldVal) or delta from current value.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.