Skip to main content
Talentd

Range Sum Query - Mutable - Solution & Explanation

MediumArrayDesignBinary Indexed TreeSegment Tree14 min readAsked at: Microsoft, Adobe, Google +1
Practice this problem

Problem Statement

Given an integer array nums, handle multiple queries of the following types:

  1. Update the value of an element in nums.
  2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (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] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • At most 3 * 104 calls will be made to update and sumRange.

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.

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(log n) for both update and sumRange.

Space Complexity: O(n) for the segment tree storage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force - Simple Array Modification

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.

Optimized with Segment Tree

Time Complexity: O(log n) for both update and sumRange.

Space Complexity: O(n) for the segment tree storage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ArrayUpdate: O(1), Query: O(n)O(n)Simple implementation when the array is small or range queries are infrequent
Segment TreeUpdate: O(log n), Query: O(log n)O(n)Best choice when updates and range queries both occur frequently

Video Solution

Range Sum Query - Mutable | Leetcode 307 | Segment tree construction and update • Techdose • 70,205 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Range Sum Query - Mutable with our built-in code editor and test cases.

Practice on FleetCode
Previous

Range Sum Query 2D - Mutable

Next

Range Sum Query - Immutable