Advanced · Module 19 · Lesson 4
Fenwick tree
Prefix aggregates with logarithmic updates.
Lesson 118 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Fenwick Tree
Jump through prefix blocks using lowbit
Phase
update
Built values
1/6
Active index
1
Prefix sum
—
3
i=1
0
i=2
0
i=3
0
i=4
0
i=5
0
i=6
Why this step happens
Index 1 summarizes a range containing original index 1.
tree[i] stores the sum of the range ending at i with length lowbit(i).
Theory lesson · Step-by-step
Understand Fenwick tree
Prefix aggregates with logarithmic updates.
Worked approach
Trace the reasoning step by step
- 1For update, add delta and advance by i & -i.
- 2For prefix query, accumulate and remove i & -i.
- 3Convert a range query into two prefixes.
- 4Use one-based indexing.
Concrete example
Store [2,1,3,4] and query prefix sum through index 3.
- 1Follow parent links while building partial sums.
- 2Query moves index downward by its lowest set bit.
Prefix sum is 6 in O(log n).
What must remain true (Loop Invariant)
tree[i] stores an aggregate over the range determined by the least-significant set bit of i.
Cost Model
Complexity & Trade-offs
When to use it
- Large constraints requiring specialized string, range, geometry, or network tools.
- Repeated queries or updates that justify preprocessing.
- Problems with a strong algebraic, heuristic, or residual invariant.
Common mistakes
- Using a specialized structure without checking its operation assumptions.
- Mixing zero-based and one-based indexes.
- Memorizing formulas without proving what each stored value means.
Practice prompts
- Reproduce the worked Fenwick tree example without looking at the trace.
- Change one input condition and explain whether the Fenwick tree invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check