Intermediate LevelData Structures & Algorithms
What is a Fenwick Tree (Binary Indexed Tree) and how does it work?
ā Interview Prompt: Explain Binary Indexed Tree (BIT/Fenwick Tree), O(log N) prefix sum and point update operations, and the lowbit trick.
A Fenwick Tree (BIT) provides $O(\log N)$ prefix sum queries and point updates, with $O(N)$ space ā simpler to implement than a Segment Tree.
Core Idea: Lowbit Trick
Each index $i$ is responsible for a range of length equal to its lowest set bit (i & (-i)).
ā¢
Update: Add delta to index $i$ and propagate to all ancestors:
i += i & (-i).ā¢
Query (prefix sum 1..i): Sum contributions while moving to parent:
i -= i & (-i).Code Implementation Example
typescript
class FenwickTree {
private tree: number[];
constructor(private n: number) {
this.tree = new Array(n + 1).fill(0);
}
update(i: number, delta: number): void { // 1-indexed
for (; i <= this.n; i += i & (-i))
this.tree[i] += delta;
}
query(i: number): number { // prefix sum [1..i]
let sum = 0;
for (; i > 0; i -= i & (-i))
sum += this.tree[i];
return sum;
}
rangeQuery(l: number, r: number): number {
return this.query(r) - this.query(l - 1);
}
}š”Fenwick Tree with O(log N) point update and prefix sum query.
šÆ Interview Key Takeaway
Fenwick Tree is simpler to code than a Segment Tree but limited to associative-invertible operations (sum, XOR). Not suitable for range min/max without modifications.
#DSA#Fenwick Tree#BIT#Range Queries#Intermediate
Back to all Data Structures & Algorithms Questionsā