# Range Sum Query - Immutable
**Difficulty:** EASY
[External](https://leetcode.com/problems/range-sum-query-immutable)
Canonical: https://scaleengineer.com/dsa/problems/range-sum-query-immutable
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
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`.

# Approaches
## Brute Force - Calculate Sum for Each Query
The most straightforward approach is to calculate the sum for each query by iterating through the range from left to right index. This approach doesn't require any preprocessing but has poor performance for multiple queries.
**Time:** O(n) per query, where n is the length of the range (right - left + 1). Constructor: O(1) · **Space:** O(1) additional space (only storing reference to original array)
**Pros:** Simple to understand and implement; No additional space required beyond storing the original array; No preprocessing time needed
**Cons:** Inefficient for multiple queries; Time complexity grows linearly with range size; Redundant calculations for overlapping ranges
### Explanation
For each `sumRange(left, right)` query, we iterate through the array from index `left` to `right` and accumulate the sum. This is the most naive approach where we don't store any additional information and compute the sum fresh for every query.

```java
class NumArray {
    private int[] nums;
    
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
```

This approach is simple to implement but becomes inefficient when we have many queries, especially for large ranges.
### Algorithm
1. Store the original array in the constructor
2. For each `sumRange(left, right)` query:
   - Initialize sum to 0
   - Iterate from index `left` to `right`
   - Add each element to the sum
   - Return the accumulated sum

## Prefix Sum Array - Optimal Solution
The optimal approach uses a prefix sum array to precompute cumulative sums. This allows us to answer any range sum query in constant time using the formula: sum(left, right) = prefixSum[right+1] - prefixSum[left].
**Time:** O(n) for constructor preprocessing, O(1) per query where n is the length of the input array · **Space:** O(n) for storing the prefix sum array
**Pros:** Constant time query after preprocessing; Optimal for multiple queries; Simple mathematical formula for range sum; Handles edge cases naturally
**Cons:** Requires additional space for prefix sum array; Preprocessing time needed during construction; Not suitable if the original array changes frequently
### Explanation
We precompute a prefix sum array where `prefixSum[i]` represents the sum of elements from index 0 to i-1. This preprocessing allows us to answer any range query in O(1) time using the mathematical property that the sum of elements from index `left` to `right` equals `prefixSum[right+1] - prefixSum[left]`.

```java
class NumArray {
    private int[] prefixSum;
    
    public NumArray(int[] nums) {
        prefixSum = new int[nums.length + 1];
        // prefixSum[0] = 0 (sum of no elements)
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
}
```

The key insight is that if we know the cumulative sum up to any index, we can find the sum of any subarray by subtracting the cumulative sum before the start of our range from the cumulative sum at the end of our range.
### Algorithm
1. In constructor:
   - Create a prefix sum array of size n+1
   - Set prefixSum[0] = 0
   - For each index i from 0 to n-1:
     - prefixSum[i+1] = prefixSum[i] + nums[i]
2. For each `sumRange(left, right)` query:
   - Return prefixSum[right+1] - prefixSum[left]

# Solutions
### Java

```java
class NumArray { private int [] s ; public NumArray ( int [] nums ) { int n = nums . length ; s = new int [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } } public int sumRange ( int left , int right ) { return s [ right + 1 ] - s [ left ]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */
```

### JavaScript

```javascript
/** * @param {number[]} nums */ var NumArray = function (nums) {
  const n = nums.length;
  this.s = Array(n + 1).fill(0);
  for (let i = 0; i < n; ++i) {
    this.s[i + 1] = this.s[i] + nums[i];
  }
};
/** * @param {number} left * @param {number} right * @return {number} */ NumArray.prototype.sumRange =
  function (left, right) {
    return this.s[right + 1] - this.s[left];
  }; /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(left,right) */

```

### CPP

```cpp
class NumArray { public: NumArray ( vector < int >& nums ) { int n = nums . size (); s . resize ( n + 1 ); for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } } int sumRange ( int left , int right ) { return s [ right + 1 ] - s [ left ]; } private: vector < int > s ; }; /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj->sumRange(left,right); */
```

### Python

```python
''' >>> from itertools import accumulate >>> accumulate([1,2,3]) <itertools.accumulate object at 0x108f38340> >>> list(accumulate([1,2,3])) [1, 3, 6] >>> list(accumulate([1,2,3], initial=0)) [0, 1, 3, 6] >>> list(accumulate([1,2,3], initial=10)) [10, 11, 13, 16] ''' # note: when using python2, I always got error when importing it, via itertools.accumulate() # switching to python3, then all good for itertools.accumulate() class NumArray : def __init__ ( self , nums : List [ int ]): self . s = list ( accumulate ( nums , initial = 0 )) def sumRange ( self , left : int , right : int ) -> int : return self . s [ right + 1 ] - self . s [ left ] # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # param_1 = obj.sumRange(left,right) ############ class NumArray ( object ): def __init__ ( self , nums ): """ initialize your data structure here. :type nums: List[int] """ self . dp = [ 0 ] * ( len ( nums ) + 1 ) for i in range ( 0 , len ( nums )): self . dp [ i + 1 ] = self . dp [ i ] + nums [ i ] def sumRange ( self , i , j ): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ return self . dp [ j + 1 ] - self . dp [ i ] # Your NumArray object will be instantiated and called as such: # numArray = NumArray(nums) # numArray.sumRange(0, 1) # numArray.sumRange(1, 2)
```