#307
Range Sum Query - Mutable
Medium Fenwick tree (BIT)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Support two operations on an array: update one element, and return the sum of a range. Both must be fast.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: change single values and ask range sums, both fast.
Why this works: a Fenwick tree updates and sums prefixes in O(log n); a range sum is the difference of two prefix sums.
Example: [1, 3, 5]
sum(0..2) = 9update index 1 to 2 → add -1sum(0..2) = 8
✦Hints open one at a time
A prefix-sum array makes queries O(1) but updates O(n).
A Fenwick tree (Binary Indexed Tree) does both in O(log n).
i & -i is the lowest set bit — it decides how far each step jumps.
↗Approach
Keep a 1-indexed tree array. add(i, delta) walks i += i & −i; prefix(i) walks i −= i & −i. update stores the old value to compute delta; sumRange = prefix(r + 1) − prefix(l).
</>Solution (Java)
class NumArray {
private final int[] nums, tree;
public NumArray(int[] nums) {
this.nums = nums.clone();
tree = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) add(i + 1, nums[i]);
}
public void update(int index, int val) {
add(index + 1, val - nums[index]); // add the difference
nums[index] = val;
}
public int sumRange(int left, int right) {
return prefix(right + 1) - prefix(left);
}
private void add(int i, int delta) {
for (; i < tree.length; i += i & -i) tree[i] += delta;
}
private int prefix(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
}!Common mistake
Passing the new value to add() instead of the difference from the old value.
Complexity
- Time: O(log n) per update and query; O(n log n) to build.
- Space: O(n).
Topic: Segment Tree, Fenwick & Sparse Table
🎬 Episodes 98–100: video coming soon