Prefix Sum Queries
The main operation of a Fenwick tree is prefix sum query: given an index i, return the sum of elements from 1 to i (inclusive). We compute this by iterating while i > 0: add tree[i], then subtract the LSB (i -= i & -i).
Java implementation for prefix sum:
public int prefixSum(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= idx & -idx;
}
return sum;
}
Range sum from L to R can be obtained as prefixSum(R) - prefixSum(L-1).
Point update: Add delta to element at index idx. Propagate by adding delta to tree[i] for all i = idx, idx + LSB, idx + LSB of that, etc., while i ≤ n.
public void update(int idx, int delta) {
while (idx <= n) {
tree[idx] += delta;
idx += idx & -idx;
}
}
Both operations run in O(log n).
Two Minute Drill
- Prefix sum query: O(log n) using LSB subtraction.
- Range sum: prefixSum(R) - prefixSum(L-1).
- Point update: add delta to all nodes covering the index (propagate using LSB addition).
- Time O(log n) for both operations.
Need more clarification?
Drop us an email at career@quipoinfotech.com