Range Sum Query - Mutable
Range Sum Query - Mutable is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (fenwick tree), runs in O(log n) per call, O(n log n) to build time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (plain array) up.
Problem
Build a class NumArray over an integer array that supports two kinds of operations, mixed in any order.
NumArray(int[] nums) stores the starting array. update(int index, int val) sets nums[index] to val. sumRange(int left, int right) returns the sum of the elements from index left to index right, both included, using the current values.
Examples
Example 1
- Input
NumArray([2, 5, -3, 4]), sumRange(0, 3), update(2, 6), sumRange(1, 2), sumRange(0, 3)- Output
8, 11, 17- Why
- Initially 2 + 5 - 3 + 4 = 8. After index 2 becomes 6, the range [1, 2] is 5 + 6 = 11 and the whole array sums to 17.
Example 2
- Input
NumArray([10]), sumRange(0, 0), update(0, -4), sumRange(0, 0)- Output
10, -4- Why
- A one-element array: the range sum is just that element, before and after it changes.
Constraints
1 <= nums.length <= 3 * 10^4-100 <= nums[i], val <= 1000 <= index < nums.lengthand0 <= left <= right < nums.length- At most
3 * 10^4calls toupdateandsumRangein total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (plain array) | O(1) update, O(n) sumRange | O(n) |
| Optimal (Fenwick tree) | O(log n) per call, O(n log n) to build | O(n) |
1Brute force (plain array)
O(1) update, O(n) sumRangeA query may scan the whole array; an update touches one slot.O(n)One copy of the array.Keep a copy of the array. Updates overwrite one slot; each range query loops over the range and adds it up.
- Constructor: copy nums.
- update(index, val): a[index] = val.
- sumRange(left, right): add a[left..right] and return it.
class NumArray {
private final int[] a;
public NumArray(int[] nums) {
a = nums.clone();
}
public void update(int index, int val) {
a[index] = val;
}
public int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) sum += a[i];
return sum;
}
}class NumArray:
def __init__(self, nums: List[int]):
self.a = list(nums)
def update(self, index: int, val: int) -> None:
self.a[index] = val
def sumRange(self, left: int, right: int) -> int:
return sum(self.a[left:right + 1])class NumArray {
vector<int> a;
public:
NumArray(vector<int>& nums) : a(nums) {}
void update(int index, int val) {
a[index] = val;
}
int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) sum += a[i];
return sum;
}
};class NumArray {
constructor(nums) {
this.a = nums.slice();
}
update(index, val) {
this.a[index] = val;
}
sumRange(left, right) {
let sum = 0;
for (let i = left; i <= right; i++) sum += this.a[i];
return sum;
}
}2Optimal (Fenwick tree)
O(log n) per call, O(n log n) to buildEach walk changes one bit of the index per step, so at most log n steps.O(n)The tree and the value array, each n + 1 entries.A Fenwick tree stores in tree[i] (1-indexed) the sum of the block of length i & -i that ends at i. A prefix sum walks down by removing the lowest set bit; an update walks up by adding it. Keep the current values in a side array so update(index, val) can add val - old as a difference. sumRange(l, r) = prefix(r + 1) - prefix(l).
- Constructor: tree of size n + 1; for each i add nums[i] at position i + 1.
- add(i, delta): while i <= n: tree[i] += delta; i += i & -i.
- prefix(i): sum = 0; while i > 0: sum += tree[i]; i -= i & -i.
- update: delta = val - a[index]; a[index] = val; add(index + 1, delta).
- sumRange: prefix(right + 1) - prefix(left).
class NumArray {
private final int n;
private final int[] tree;
private final int[] a;
public NumArray(int[] nums) {
n = nums.length;
tree = new int[n + 1];
a = nums.clone();
for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}
private void add(int i, int delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
private int prefix(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
public void update(int index, int val) {
add(index + 1, val - a[index]);
a[index] = val;
}
public int sumRange(int left, int right) {
return prefix(right + 1) - prefix(left);
}
}class NumArray:
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [0] * (self.n + 1)
self.a = list(nums)
for i, x in enumerate(nums):
self._add(i + 1, x)
def _add(self, i: int, delta: int) -> None:
while i <= self.n:
self.tree[i] += delta
i += i & -i
def _prefix(self, i: int) -> int:
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i
return total
def update(self, index: int, val: int) -> None:
self._add(index + 1, val - self.a[index])
self.a[index] = val
def sumRange(self, left: int, right: int) -> int:
return self._prefix(right + 1) - self._prefix(left)class NumArray {
int n;
vector<int> tree, a;
void add(int i, int delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
int prefix(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
public:
NumArray(vector<int>& nums) : n(nums.size()), tree(nums.size() + 1, 0), a(nums) {
for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}
void update(int index, int val) {
add(index + 1, val - a[index]);
a[index] = val;
}
int sumRange(int left, int right) {
return prefix(right + 1) - prefix(left);
}
};class NumArray {
constructor(nums) {
this.n = nums.length;
this.tree = new Array(this.n + 1).fill(0);
this.a = nums.slice();
for (let i = 0; i < this.n; i++) this.add(i + 1, nums[i]);
}
add(i, delta) {
for (; i <= this.n; i += i & -i) this.tree[i] += delta;
}
prefix(i) {
let sum = 0;
for (; i > 0; i -= i & -i) sum += this.tree[i];
return sum;
}
update(index, val) {
this.add(index + 1, val - this.a[index]);
this.a[index] = val;
}
sumRange(left, right) {
return this.prefix(right + 1) - this.prefix(left);
}
}Edge cases to test
- A range of a single index (left == right)
- Updating an index to the value it already has
- Updating the first or last index, then querying the full array
- Many updates in a row with no queries in between
Hints
Hint 1
A plain array makes updates O(1) and sums O(n); a prefix-sum array does the opposite. Can both be O(log n)?
Hint 2
Store partial sums of blocks whose sizes are powers of two. A prefix sum is then a sum of O(log n) blocks, and an index belongs to O(log n) blocks.
Hint 3
A Fenwick (binary indexed) tree does exactly that: i & -i is the length of the block that ends at position i. Turn update into 'add the difference'.
FAQ
What is the best time complexity for Range Sum Query - Mutable?
Optimal (Fenwick tree) runs in O(log n) per call, O(n log n) to build time and O(n) extra space. Each walk changes one bit of the index per step, so at most log n steps.
Which pattern does Range Sum Query - Mutable use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Range Sum Query - Mutable?
Yes. Brute force (plain array) takes O(1) update, O(n) sumRange time and O(n) space. Keep a copy of the array.
Which edge cases should I test for Range Sum Query - Mutable?
A range of a single index (left == right); Updating an index to the value it already has; Updating the first or last index, then querying the full array; Many updates in a row with no queries in between.