Fenwick Tree (Binary Indexed Tree)
Software Engineer path · lesson 20 of 99A simpler, more space-efficient alternative to Segment Tree for prefix sums and point updates. Uses bit manipulation for elegant O(log n) operations.
Syntax: prefix n · range n n · add n n. Numbers from -50 to 50.
2–8 whole numbers between −50 and 50.
Build the tree by adding each value with update(); 8 values.
- 1update(i, delta): # 1-based
- 2 while i <= n: bit[i] += delta; i += i & -i # climb
- 3prefix(i):
- 4 s = 0; while i > 0: s += bit[i]; i -= i & -i # drop the lowest bit
- 5range(l, r) = prefix(r) - prefix(l - 1)
- Index jumps
- 0 / 27
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Prefix sum query
Order the steps of query(i) on a Fenwick tree.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
What does i & (-i) compute?
The short version
Like a skip list for sums. Instead of storing every prefix sum, you store clever partial sums at specific positions. Using binary representation, you can 'hop' through just log(n) positions to get any prefix sum.
In more depth
Elegant Bit Manipulation
Fenwick Tree (BIT) achieves the same query/update complexity as Segment Tree with simpler code and less space.
Core Operations:
Update(i, delta):
while i <= n:
tree[i] += delta
i += i & (-i) // Move to parent
Query(i): // Sum from 1 to i
sum = 0
while i > 0:
sum += tree[i]
i -= i & (-i) // Move to predecessorRange Query: sum(l, r) = Query(r) - Query(l-1)
Key Gotchas:
When to reach for this
- Prefix sum queries + point updates
- Counting inversions
- Dynamic rank queries
- Simpler than Segment Tree when range updates not needed
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required