What is a Fenwick Tree (Binary Indexed Tree)?
Learn what a Fenwick tree (binary indexed tree) is, how prefix-sum queries and updates work in O(log n), and how to explain it in interviews.
Expected Interview Answer
A Fenwick tree, or binary indexed tree, is an array-backed structure that answers prefix-sum queries and supports point updates in O(log n) time using O(n) space, by exploiting the binary representation of indices to store partial sums at strategic positions.
Each index i in the underlying array stores the sum of a range whose length equals the lowest set bit of i. To query a prefix sum up to index i, you repeatedly subtract the lowest set bit and accumulate, walking O(log n) steps. To update a single element, you repeatedly add the lowest set bit and adjust every ancestor's stored sum, again O(log n) steps. This gives a much smaller memory footprint and simpler implementation than a full segment tree, at the cost of being naturally limited to prefix-sum-style associative operations rather than arbitrary range queries. It is a staple for competitive programming problems involving cumulative frequency counts, inversion counting, and range-sum-with-point-update workloads.
- O(log n) point update and prefix-sum query
- O(n) space, far leaner than a segment tree
- Simple iterative implementation via bit tricks
- Ideal for cumulative frequency and inversion counting
AI Mentor Explanation
A Fenwick tree is like a scoreboard operator who never re-adds every run scored this innings from ball one. Instead, certain checkpoint totals are kept, each covering a power-of-two-sized block of overs, so a running total up to the current over is built by combining just a handful of those checkpoints rather than summing every ball. When a single run is corrected after review, only the checkpoints whose block includes that ball get nudged, not the whole scoresheet. This checkpoint trick is why the total-runs-so-far figure updates almost instantly even deep into a long innings.
Step-by-Step Explanation
Step 1
Size the tree
Allocate an array of size n+1 (1-indexed), initialized to zero.
Step 2
Update: add lowest set bit
To add a value at index i, update tree[i] and repeatedly move to i += (i & -i) until past n.
Step 3
Query: subtract lowest set bit
To get the prefix sum up to index i, accumulate tree[i] and move to i -= (i & -i) until 0.
Step 4
Derive range sums
A range sum from l to r is query(r) minus query(l-1), both O(log n).
What Interviewer Expects
- Explain the lowest-set-bit (i & -i) trick behind both update and query
- State O(log n) for both point update and prefix query
- Compare space and simplicity against a segment tree
- Give a real use case: cumulative frequency, inversion counting, range-sum-with-update
Common Mistakes
- Forgetting the structure is 1-indexed, causing off-by-one bugs at index 0
- Confusing a Fenwick tree with a segment tree and assuming it handles arbitrary range queries
- Not knowing i & -i isolates the lowest set bit
- Claiming O(1) update instead of O(log n)
Best Answer (HR Friendly)
“A Fenwick tree is a compact array trick that lets me get a running total up to any point, and update any single value, both in logarithmic time instead of re-adding everything each time. I reach for it whenever I need fast cumulative sums with frequent updates, like counting inversions or tracking running totals in a stream.”
Code Example
class FenwickTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def prefix_sum(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
def range_sum(self, l, r):
return self.prefix_sum(r) - self.prefix_sum(l - 1)
ft = FenwickTree(10)
ft.update(3, 5)
ft.update(7, 2)
print(ft.range_sum(1, 7)) # 7Follow-up Questions
- How would you count inversions in an array using a Fenwick tree?
- How does a Fenwick tree compare to a segment tree in capability and space?
- How would you extend a Fenwick tree to support range updates and range queries?
- How would you build a 2D Fenwick tree for a grid of point updates?
MCQ Practice
1. What is the time complexity of a point update and a prefix-sum query in a Fenwick tree?
Both operations walk O(log n) steps by repeatedly adding or subtracting the lowest set bit of the index.
2. What does the expression i & (-i) compute in a Fenwick tree implementation?
i & (-i) isolates the lowest set bit, which determines the range each index is responsible for.
3. Compared to a segment tree, a Fenwick tree is best described as?
A Fenwick tree trades generality for a smaller, simpler array-based implementation focused on prefix sums.
Flash Cards
What does a Fenwick tree efficiently support? — Point updates and prefix-sum queries, both in O(log n).
What bit trick powers Fenwick tree traversal? — i & (-i), which isolates the lowest set bit of the index.
What is the space complexity of a Fenwick tree? — O(n), a single array of size n+1.
Name a classic use case for a Fenwick tree. — Counting inversions in an array, or maintaining cumulative frequency counts.