Range Sum Query - Mutable
Problem
Support update(i, val) (point write) and sumRange(l, r) (range query) on an integer array.
nums = [1,3,5]; sumRange(0,2); update(1,2); sumRange(0,2)[9, 8]class NumArray:
def __init__(self, nums):
self.n = len(nums)
self.bit = [0] * (self.n + 1)
self.a = [0] * self.n
for i, x in enumerate(nums): self.update(i, x)
def update(self, i, val):
diff = val - self.a[i]; self.a[i] = val
x = i + 1
while x <= self.n: self.bit[x] += diff; x += x & -x
def _pref(self, i):
s = 0
while i > 0: s += self.bit[i]; i -= i & -i
return s
def sumRange(self, l, r):
return self._pref(r + 1) - self._pref(l)class NumArray {
constructor(nums) {
this.n = nums.length;
this.bit = new Array(this.n + 1).fill(0);
this.a = new Array(this.n).fill(0);
nums.forEach((x, i) => this.update(i, x));
}
update(i, val) {
const diff = val - this.a[i]; this.a[i] = val;
for (let x = i + 1; x <= this.n; x += x & -x) this.bit[x] += diff;
}
_pref(i) {
let s = 0;
for (; i > 0; i -= i & -i) s += this.bit[i];
return s;
}
sumRange(l, r) { return this._pref(r + 1) - this._pref(l); }
}class NumArray {
int n; int[] bit, a;
public NumArray(int[] nums) {
n = nums.length; bit = new int[n + 1]; a = new int[n];
for (int i = 0; i < n; i++) update(i, nums[i]);
}
public void update(int i, int val) {
int diff = val - a[i]; a[i] = val;
for (int x = i + 1; x <= n; x += x & -x) bit[x] += diff;
}
int pref(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
public int sumRange(int l, int r) { return pref(r + 1) - pref(l); }
}class NumArray {
int n; vector bit, a;
public:
NumArray(vector& nums) {
n = nums.size(); bit.assign(n + 1, 0); a.assign(n, 0);
for (int i = 0; i < n; i++) update(i, nums[i]);
}
void update(int i, int val) {
int diff = val - a[i]; a[i] = val;
for (int x = i + 1; x <= n; x += x & -x) bit[x] += diff;
}
int pref(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
int sumRange(int l, int r) { return pref(r + 1) - pref(l); }
}; Explanation
We need to both change single values and ask for the sum of a range, many times. A plain array makes one fast but the other slow. A Binary Indexed Tree (also called a Fenwick tree) makes both quick.
The trick is that each slot bit[x] secretly stores the sum of a small chunk of the array whose size is x & -x (the lowest set bit of x). To get the sum of the first i elements we keep jumping down by that lowest bit, adding pieces as we go.
For an update(i, val) we first compute how much the value changed (diff), then walk up the tree adding diff to every chunk that covers index i, each time stepping x += x & -x. Both walks touch only about log n slots.
A range sum is just two prefix sums: sumRange(l, r) = pref(r+1) - pref(l), since the second cancels everything before l.
Example: nums = [1, 3, 5]. sumRange(0, 2) is pref(3) - pref(0) = 9. After update(1, 2) the value at index 1 drops by 1, so the next sumRange(0, 2) returns 8.