Skip to main content
Talentd

Range Sum Query - Immutable - Solution & Explanation

EasyArrayDesignPrefix Sum23 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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

  1. 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.
  • 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", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

 

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= left <= right < nums.length
  • At most 104 calls will be made to sumRange.

Approach Overview

Problem Overview: You receive an integer array and must answer multiple queries asking for the sum of elements between two indices left and right (inclusive). The array never changes after initialization, so the challenge is designing a structure that answers range sum queries efficiently.

Approach 1: Brute Force Iteration (O(n) per query, O(1) space)

The simplest method recomputes the sum for every query. Iterate from index left to right and accumulate the values. Each query scans a portion of the array, so the time complexity is O(n) in the worst case per query. This approach requires no preprocessing and only constant extra space, but performance quickly degrades when many queries are executed. It mainly serves as a baseline that demonstrates why preprocessing is useful.

Approach 2: Prefix Sum Array (O(n) preprocessing, O(1) query, O(n) space)

The optimal solution precomputes cumulative sums using a prefix sum array. During initialization, build an array where prefix[i] stores the sum of elements from index 0 through i. Once built, any query can be answered using subtraction: sum(left, right) = prefix[right] - prefix[left - 1] (with a small edge-case check when left = 0). Preprocessing runs once in O(n), and every query becomes a constant-time lookup. This works well because the underlying array never changes.

Approach 3: Segment Tree (O(n) build, O(log n) query, O(n) space)

A segment tree stores range sums in a balanced tree structure where each node represents the sum of a segment of the array. Queries traverse only the nodes that overlap with the requested range, producing a time complexity of O(log n). This structure is powerful when the array supports updates because modifications can also be handled in O(log n). In this specific problem the array is immutable, so the segment tree is more complex than necessary compared to prefix sums.

Recommended for interviews: Prefix sum is the expected solution. Interviewers want to see that you recognize the array never changes and trade a one-time preprocessing step for constant-time queries. Mentioning the brute force approach first shows you understand the baseline, while implementing prefix sums demonstrates algorithmic optimization and familiarity with a common pattern used in many range query problems.

Approach 1: Prefix Sum Array

The key idea in this approach is to use a prefix sum array. We precompute cumulative sums such that each element at index i in this prefix array contains the sum of all elements in the nums array from index 0 to i. The sum of a subarray can then be computed in constant time using the relation: sumRange(left, right) = prefixSum[right] - prefixSum[left-1]. This pre-computation allows each query to be answered in O(1) time after O(n) pre-computation.

This C solution defines a structure NumArray that contains the prefix sums array. In the numArrayCreate function, we allocate memory for the prefix sums and fill it such that each entry in the array contains the cumulative sum up to that index. The numArraySumRange function then computes the sum of any given range using precomputed values.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for precomputing the prefix sums, O(1) for each range query.
Space Complexity: O(n) for storing the prefix sums.

Try this approach in the editor →

Approach 2: Segment Tree

A Segment Tree is a data structure that allows efficient range query and update operations. It is particularly useful in scenarios where there are multiple queries of the dynamic array that could change over time. For sumRange queries, the segment tree helps to retrieve the sum in logarithmic time, and it can be further extended to handle updates if needed.

This C solution involves a Segment Tree built in a bottom-up manner. The buildTree function constructs the tree. During a sumRange query, the results from relevant nodes are combined. numArrayFree is used to clean resources.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for building the tree, O(log n) per query.
Space Complexity: O(n) for the segment tree.

Try this approach in the editor →

Approach 3: Prefix Sum

We create a prefix sum array s of length n + 1, where s[i] represents the prefix sum of the first i elements, that is, s[i] = sum_{j=0}^{i-1} nums[j]. Therefore, the sum of the elements between the indices [left, right] can be expressed as s[right + 1] - s[left].

The time complexity for initializing the prefix sum array s is O(n), and the time complexity for querying is O(1). The space complexity is O(n).

Code

PythonJavaC++GoTypeScriptRustJavaScriptPHPCKotlin

Python

Java

C++

Go

TypeScript

Rust

JavaScript

PHP

C

Kotlin

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum Array

Time Complexity: O(n) for precomputing the prefix sums, O(1) for each range query.
Space Complexity: O(n) for storing the prefix sums.

Segment Tree

Time Complexity: O(n) for building the tree, O(log n) per query.
Space Complexity: O(n) for the segment tree.

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force IterationO(n) per queryO(1)Small input sizes or very few queries
Prefix Sum ArrayO(n) build, O(1) queryO(n)Best choice when the array is immutable and queries are frequent
Segment TreeO(n) build, O(log n) queryO(n)Useful if range queries and updates both need to be supported

Video Solution

Range Sum Query Immutable - Leetcode 303 - Python • NeetCodeIO • 44,640 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Range Sum Query - Immutable easy or hard?
Range Sum Query - Immutable is categorized as an Easy problem on LeetCode with an acceptance rate above 70%. The main concept is understanding prefix sums and recognizing when preprocessing can reduce repeated work in multiple queries.
How to solve Range Sum Query - Immutable in O(n)?
Build a prefix sum array where each index stores the cumulative sum up to that position. After this O(n) preprocessing step, compute any range sum in constant time using subtraction of prefix values. This converts repeated summation work into simple arithmetic lookups.
Range Sum Query - Immutable Python or Java solution?
Most implementations create a prefix array during object initialization and compute sums in the sumRange function. Python, Java, C++, and JavaScript solutions all follow the same logic: preprocess cumulative sums once and answer queries with constant-time subtraction.
What is the best approach for Range Sum Query - Immutable?
The prefix sum array approach is the most efficient for this problem. Precompute cumulative sums in O(n) time, then answer each range query in O(1) using prefix[right] - prefix[left-1]. Because the array never changes, prefix sums eliminate repeated scanning of elements.
What data structure is used in Range Sum Query - Immutable?
The most common structure is a prefix sum array that stores cumulative totals for fast lookups. A segment tree can also be used for range queries, though it is typically unnecessary when the array is immutable and updates are not required.
What is the time complexity of Range Sum Query - Immutable?
Using the optimal prefix sum solution, preprocessing takes O(n) time and each query runs in O(1). The brute force method requires O(n) time per query, while a segment tree answers queries in O(log n) after O(n) preprocessing.
Is Range Sum Query - Immutable asked at Google, Amazon, or Meta?
Range query problems using prefix sums appear frequently in interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but the prefix sum technique is a common pattern used in array and subarray sum questions.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Maximum Size Subarray Sum Equals k

Next

Range Sum Query 2D - Immutable