Range Sum Query - Mutable solution and explanation
Google
9 more videos on this problem
Range Sum Query - Mutable | Leetcode 307 | Segment tree construction and updateTechdose · 26:32 · 70K views
Range Sum Query - Mutable | Leetcode 307 | Segment Tree Concepts & Qns | Video 8 | codestorywithMIKcodestorywithMIK · 17:18 · 15K views
Segment Tree Basics Range Sum Query - Mutable | Leetcode 307 | Live coding sessionCoding Decoded · 15:51 · 9K views
LeetCode 307. Range Sum Query - MutableHappy Coding · 33:30 · 4K views
Fenwick Tree (BIT Tree) Leetcode 307 | Range Sum Query - MutableNideesh Terapalli · 29:33 · 3K views
Leetcode - Range Sum Query - Mutable (Python)Timothy H Chang · 8:29 · 3K views
Daily Leetcode #852: Jul 31, 2022 - 307. Range Sum Query - MutableProgramming Live with Larry · 7:27 · 1K views
Daily Leetcode #444: Jun 18, 2021 - 307. Range Sum Query - MutableProgramming Live with Larry · 24:04 · 386 views
【Binary Indexed Tree】307. Range Sum Query - Mutablehappygirlzt · 15:59 · 285 views
LeetCode - 307. Range Sum Query - Mutable | Binary Indexed Tree | JavaOrkhan Gasanov · 10:54 · 270 views
The problem
Given an integer array nums, handle multiple queries of the following types:
- Update the value of an element in
nums. - Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.void update(int index, int val)Updates the value ofnums[index]to beval.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] Output [null, 9, null, 8] Explanation NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1, 2, 5] numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
Constraints:
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length- At most
3 * 104calls will be made toupdateandsumRange.
Approach overview
Problem Overview: You need to design a data structure that supports two operations on an integer array: update the value at a specific index and return the sum of elements within a range [left, right]. The challenge comes from handling frequent updates efficiently while still answering range queries quickly.
Approach 1: Brute Force - Simple Array Modification (Update O(1), Query O(n))
The simplest design stores the numbers directly in an array. When update(index, val) is called, you replace the value at that index in O(1) time. For sumRange(left, right), iterate from left to right and accumulate the sum. This approach works because array access is constant time, but every query requires scanning part of the array. Time complexity becomes O(n) per query and O(1) per update, with O(n) space for the array. It works for small inputs or when queries are rare, but it becomes slow when many range queries are executed.
Approach 2: Segment Tree (Update O(log n), Query O(log n))
A segment tree stores aggregated sums of subranges in a binary tree structure. Each node represents the sum of a segment of the array, and its children represent smaller segments. Building the tree takes O(n) time. When you update a value, the change propagates from the leaf node up to the root, updating all affected segment sums in O(log n) time. For sumRange(left, right), the query walks the tree and combines sums from nodes that fully cover parts of the requested range, also in O(log n) time.
This structure avoids scanning the array repeatedly. Instead of recalculating sums from scratch, it reuses precomputed segment sums. Segment trees are ideal when the array is frequently modified and queries are frequent. They provide a balanced tradeoff: logarithmic time for both operations and O(n) memory.
Another common alternative is a Binary Indexed Tree (Fenwick Tree), which also supports prefix sums and updates in O(log n). Many engineers prefer it for simpler implementation, but segment trees provide more flexibility for advanced range operations. Both approaches rely on understanding prefix aggregation over an array.
Recommended for interviews: Start by explaining the brute force array solution to show baseline reasoning. Then move to the segment tree optimization. Interviewers expect a logarithmic-time data structure because the problem mixes updates and range queries. Demonstrating how updates propagate through the tree and how queries combine partial segments shows strong understanding of range query data structures.
Approach 1: Brute Force - Simple Array Modification
This approach utilizes a simple array to store the elements, implementing updates directly and calculating the range sum by iterating through the specified range.
The update operation runs in constant time as it simply replaces a value at a given index. However, the sum operation runs in O(n) time, where n is the size of the query range, as it sums elements one by one.
class NumArray:
def __init__(self, nums):
self.nums = nums
def update(self, index, val):
self.nums[index] = val
def sumRange(self, left, right):
return sum(self.nums[left:right+1])class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public void update(int index, int val) {
nums[index] = val;
}
public int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums[i];
}
return sum;
}
}#include <vector>
using namespace std;
class NumArray {
private:
vector<int> nums;
public:
NumArray(vector<int>& nums) : nums(nums) {}
void update(int index, int val) {
nums[index] = val;
}
int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; ++i) {
sum += nums[i];
}
return sum;
}
};class NumArray {
constructor(nums) {
this.nums = nums;
}
update(index, val) {
this.nums[index] = val;
}
sumRange(left, right) {
let sum = 0;
for (let i = left; i <= right; i++) {
sum += this.nums[i];
}
return sum;
}
}#include <stdlib.h>
typedef struct {
int* nums;
int size;
} NumArray;
NumArray* numArrayCreate(int* nums, int numsSize) {
NumArray* numArray = (NumArray*) malloc(sizeof(NumArray));
numArray->nums = (int*) malloc(numsSize * sizeof(int));
numArray->size = numsSize;
for (int i = 0; i < numsSize; i++) {
numArray->nums[i] = nums[i];
}
return numArray;
}
void numArrayUpdate(NumArray* obj, int index, int val) {
obj->nums[index] = val;
}
int numArraySumRange(NumArray* obj, int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += obj->nums[i];
}
return sum;
}
void numArrayFree(NumArray* obj) {
free(obj->nums);
free(obj);
}public class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public void Update(int index, int val) {
nums[index] = val;
}
public int SumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums[i];
}
return sum;
}
}In this Python solution, we define a list self.nums to store the numbers. The update method modified a specific index with a new value, while sumRange calculates the sum of numbers between indices left and right (inclusive) by using Python's built-in sum() function.
Time Complexity: O(1) for update, O(n) for sumRange where n is the number of elements between left and right.
Space Complexity: O(1) - additional space usage is minimal.
Approach 2: Optimized with Segment Tree
A segment tree provides a more efficient solution for this problem, reducing the time complexity for both update and sum operations. Segment trees are ideal for scenarios where an array undergoes frequent updates and queries, as they allow modifications and range sum queries to be done in logarithmic time.
class NumArray:
def __init__(self, nums):
self.nums = nums
self.n = len(nums)
self.tree = [0] * (2 * self.n)
self.buildSegmentTree()
def buildSegmentTree(self):
# Build the segment tree
for i in range(self.n):
self.tree[self.n + i] = self.nums[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, pos, value):
pos += self.n
self.tree[pos] = value
while pos > 1:
pos //= 2
self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
def sumRange(self, left, right):
left += self.n
right += self.n
sum_ = 0
while left <= right:
if left % 2 == 1:
sum_ += self.tree[left]
left += 1
if right % 2 == 0:
sum_ += self.tree[right]
right -= 1
left //= 2
right //= 2
return sum_#include <vector>
using namespace std;
class NumArray {
private:
vector<int> tree;
int n;
public:
NumArray(vector<int>& nums) {
n = nums.size();
tree.resize(2 * n);
buildSegmentTree(nums);
}
void buildSegmentTree(vector<int>& nums) {
for (int i = 0; i < n; i++) {
tree[n + i] = nums[i];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
void update(int index, int val) {
index += n;
tree[index] = val;
while (index > 1) {
index /= 2;
tree[index] = tree[2 * index] + tree[2 * index + 1];
}
}
int sumRange(int left, int right) {
left += n;
right += n;
int sum = 0;
while (left <= right) {
if (left % 2 == 1) sum += tree[left++];
if (right % 2 == 0) sum += tree[right--];
left /= 2;
right /= 2;
}
return sum;
}
};This Python solution utilizes a segment tree, which allows the program to efficiently handle the updates and sum queries. The tree is represented with a flat array. The buildSegmentTree constructively sets up the tree, update modifies a value while updating the tree structure, and sumRange calculates the range sum over the tree.
Time Complexity: O(log n) for both update and sumRange.
Space Complexity: O(n) for the segment tree storage.
Approach 3: Default Approach
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, delta: number): void {
while (x <= this.n) {
this.c[x] += delta;
x += x & -x;
}
}
query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
class NumArray {
private tree: BinaryIndexedTree;
constructor(nums: number[]) {
const n = nums.length;
this.tree = new BinaryIndexedTree(n);
for (let i = 0; i < n; ++i) {
this.tree.update(i + 1, nums[i]);
}
}
update(index: number, val: number): void {
const prev = this.sumRange(index, index);
this.tree.update(index + 1, val - prev);
}
sumRange(left: number, right: number): number {
return this.tree.query(right + 1) - this.tree.query(left);
}
}
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* obj.update(index,val)
* var param_2 = obj.sumRange(left,right)
*/type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (t *BinaryIndexedTree) update(x, delta int) {
for ; x <= t.n; x += x & -x {
t.c[x] += delta
}
}
func (t *BinaryIndexedTree) query(x int) (s int) {
for ; x > 0; x -= x & -x {
s += t.c[x]
}
return s
}
type NumArray struct {
tree *BinaryIndexedTree
}
func Constructor(nums []int) NumArray {
tree := newBinaryIndexedTree(len(nums))
for i, v := range nums {
tree.update(i+1, v)
}
return NumArray{tree}
}
func (t *NumArray) Update(index int, val int) {
prev := t.SumRange(index, index)
t.tree.update(index+1, val-prev)
}
func (t *NumArray) SumRange(left int, right int) int {
return t.tree.query(right+1) - t.tree.query(left)
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* obj.Update(index,val);
* param_2 := obj.SumRange(left,right);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force - Simple Array Modification | Time Complexity: Space Complexity: |
| Optimized with Segment Tree | Time Complexity: Space Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Array | Update: O(1), Query: O(n) | O(n) | Simple implementation when the array is small or range queries are infrequent |
| Segment Tree | Update: O(log n), Query: O(log n) | O(n) | Best choice when updates and range queries both occur frequently |
Frequently asked questions
Is Range Sum Query - Mutable easy or hard?
The problem is rated Medium because it requires designing a data structure rather than writing a simple algorithm. Understanding Segment Trees or Fenwick Trees is necessary to reach the optimal O(log n) solution.
Range Sum Query - Mutable Python/Java solution
Typical implementations build a Segment Tree class with update and query methods. Python and Java solutions both maintain a tree array where each node stores the sum of a segment, allowing O(log n) updates and queries.
How to solve Range Sum Query - Mutable in O(log n)?
Use a Segment Tree or Binary Indexed Tree. Store prefix or segment sums in a tree structure so updates propagate through log n nodes. Range queries combine partial sums from relevant nodes, giving O(log n) complexity.
What is the best approach for Range Sum Query - Mutable?
Segment Tree is the most common optimal solution. It supports both update and range sum queries in O(log n) time. The tree stores sums of segments so queries combine only relevant nodes instead of scanning the array.
Is Range Sum Query - Mutable asked at Google/Amazon/Meta?
Range query data structure problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variations involving Segment Trees or Fenwick Trees are common in system design style coding rounds.
What data structure is used in Range Sum Query - Mutable?
Segment Tree and Binary Indexed Tree (Fenwick Tree) are the main data structures. Both maintain partial sums that allow fast updates and range queries without recomputing sums from scratch.
What is the time complexity of Range Sum Query - Mutable?
Using a Segment Tree, both update(index, val) and sumRange(left, right) run in O(log n) time. Building the tree initially takes O(n). The brute force array method has O(1) updates but O(n) query time.