Range Sum Query Using Prefix Sum — Problem Statement & Solution Guide

ArraysEasyPrefix Sum

TimeO(n) preprocessing + O(1) per query

SpaceO(n)

Problem Description

Implement a class named NumArray that receives an integer array at construction time and supports multiple queries asking for the sum of elements between two indices inclusive. The constructor should preprocess the array so that each query can be answered in O(1) time. The method sumRange(left,right) receives two zero‑based indices with left≤right and returns the sum of nums[left]+…+nums[right]. The solution must handle up to 10^5 elements and the same order of queries efficiently.

DSA Pattern Breakdown

"Range Sum Query Using Prefix Sum"

easy

WHY DOES IT MATTER?

Range‑sum queries appear in analytics, finance, and gaming; the prefix‑sum pattern provides the simplest O(1) answer after linear preprocessing, dramatically cutting runtime for high‑frequency queries.

OPTIMIZATION CHALLENGE

Recognizing that the sum over any interval can be expressed as the difference of two cumulative totals eliminates the need to traverse the interval each time.

REAL-WORLD CONNECTION

Think of a running total on a bank statement: the balance after each transaction is stored, so checking the total spent between two dates is just a subtraction of two balances.

Always compute the prefix array in the constructor; guard against integer overflow by using 64‑bit types when language defaults are 32‑bit.

COMPLEXITY AT A GLANCE

⏱ Time:O(n) preprocessing + O(1) per query

💾 Space:O(n)

Core Theory — Why This Approach?

Prefix sum (also called cumulative sum) transforms an array into a helper array where each entry i stores the sum of all elements up to index i. This enables constant‑time range‑sum queries because the sum of a sub‑array [l,r] can be expressed as prefix[r]‑prefix[l‑1] (with a guard for l==0). A naïve solution would iterate from l to r for each query, yielding O(n) per query; with many queries this becomes prohibitive (e.g., 10^5 queries on a 10^5‑element array leads to 10^10 operations). By preprocessing once in O(n) time to build the prefix array, each subsequent query is answered in O(1), achieving the optimal trade‑off for static arrays where updates are not required. The paradigm exemplifies the broader technique of “precompute‑once‑query‑many”, a cornerstone in algorithm design for range queries, and underlies more advanced structures like segment trees and binary indexed trees when updates are needed.

Interview Questions on This Problem

Q1How would you modify the NumArray class to support updates to individual elements while still answering range sum queries efficiently?

Introduce a Binary Indexed Tree (Fenwick) or a Segment Tree; both allow O(log n) updates and O(log n) queries by storing partial sums in a tree‑like structure.

Q2Why is the prefix‑sum approach unsuitable for a mutable array where elements can change after construction?

Because a single element change would require updating all subsequent prefix entries, leading to O(n) update time, which defeats the O(1) query guarantee.

Q3In a distributed system handling massive time‑series data, how can the prefix‑sum concept be applied to reduce latency for range aggregations?

Each shard can compute local cumulative sums; a coordinator aggregates the needed prefix values from relevant shards, turning a potentially linear scan into a few constant‑time look‑ups per shard.

Examples

Example 1

Input

NumArray([3, -2, 7, 0, 5])
sumRange(0,2)

Output

Explanation: The sub‑array from index 0 to 2 is [3,-2,7]; 3+(-2)+7=8.

Example 2

Input

NumArray([10, 20, 30, 40])
sumRange(1,3)

Output

Explanation: Elements at indices 1,2,3 are [20,30,40]; their sum is 20+30+40=90.

Example 3

Input

NumArray([-5, 0, 5, 10, -10])
sumRange(2,4)

Output

Explanation: Indices 2 to 4 give [5,10,-10]; 5+10+(-10)=5.

Constraints

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
0 <= left <= right < nums.length
Number of sumRange calls <= 100000

Optimal Approach & Strategy

Build a prefix‑sum array once in O(n) time; answer each query with two array accesses and a subtraction, achieving O(1) per query.

Brute Force Approach

Loop from left to right for each query and accumulate the sum, resulting in O(n) time per query.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n) preprocessing + O(1) per query

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.prefixSum = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        this.prefixSum[i + 1] = this.prefixSum[i] + nums[i];
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this.prefixSum[right + 1] - this.prefixSum[left];
};

// Example usage
const nums = [3, -2, 7, 0, 5];
const obj = new NumArray(nums);
console.log(obj.sumRange(0, 2)); // Output: 8
console.log(obj.sumRange(2, 4)); // Output: 12

#include <iostream>
#include <vector>
using namespace std;

class NumArray {
private:
    vector<int> prefixSum;

public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        prefixSum.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
};

int main() {
    vector<int> nums = {3, -2, 7, 0, 5};
    NumArray obj(nums);
    cout << obj.sumRange(0, 2) << endl; // Output: 8
    cout << obj.sumRange(2, 4) << endl; // Output: 12
    return 0;
}

import java.util.*;

class NumArray {
    private int[] prefixSum;
    
    public NumArray(int[] nums) {
        int n = nums.length;
        prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, -2, 7, 0, 5};
        NumArray obj = new NumArray(nums);
        System.out.println(obj.sumRange(0, 2)); // Output: 8
        System.out.println(obj.sumRange(2, 4)); // Output: 12
    }
}

class NumArray:

    def __init__(self, nums):
        self.prefixSum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefixSum[i + 1] = self.prefixSum[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.prefixSum[right + 1] - self.prefixSum[left]

# Example usage
nums = [3, -2, 7, 0, 5]
obj = NumArray(nums)
print(obj.sumRange(0, 2)) # Output: 8
print(obj.sumRange(2, 4)) # Output: 12

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.prefixSum = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        this.prefixSum[i + 1] = this.prefixSum[i] + nums[i];
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this.prefixSum[right + 1] - this.prefixSum[left];
};

// Example usage
const nums = [3, -2, 7, 0, 5];
const obj = new NumArray(nums);
console.log(obj.sumRange(0, 2)); // Output: 8
console.log(obj.sumRange(2, 4)); // Output: 12

Asked in Top Tech Interviews

Cognizant

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Range Sum Query Using Prefix Sum Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Range Sum Query Using Prefix Sum — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor