Fenwick Tree (Binary Indexed Tree)
A simpler, more space-efficient alternative to Segment Tree for prefix sums and point updates. Uses bit manipulation for elegant O(log n) operations.
Fenwick Tree (Binary Indexed Tree)
A simpler, more space-efficient alternative to Segment Tree for prefix sums and point updates. Uses bit manipulation for elegant O(log n) operations.
Input: [3, 2, -1, 6, 5, 4, -3, 3]. BIT uses bit manipulation to store partial sums. Each index i stores sum of i & (-i) elements ending at i.
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
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