In this thorough article, we will take an in-depth look at a classic problem on LeetCode, called ‘Range Sum Query – Immutable’. This problem is widely used in coding interviews and provides an opportunity to explore the concept of prefix sums and dynamic programming. We will break down the problem statement, and explore different approaches to solve this problem, analyzing their respective time and space complexities.

## Introduction

Let’s start with the problem statement:

Given an integer array `nums`

, find the sum of the elements between indices `i`

and `j`

(i ≤ j), inclusive. Implement the `NumArray`

class:

`NumArray(int[] nums)`

initializes the object with the integer array`nums`

.`int sumRange(int i, int j)`

returns the sum of the elements of the`nums`

array, inclusive, between indices`i`

and`j`

.

### Example:

Input:

`["NumArray","sumRange","sumRange","sumRange"]`

`[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]`

Output:

`[null, 1, -1, -3]`

## Understanding the Problem

The problem requires us to create a data structure that efficiently computes the sum of elements in a subarray of a given array of integers. Specifically, for multiple queries, we need to find the sum of elements between two indices, inclusive.

## Approach 1: Brute Force

The most straightforward approach would be to calculate the sum for each query by iterating through the elements between the given indices.

- For the
`NumArray`

constructor, simply store the`nums`

array. - For the
`sumRange`

method, iterate from index`i`

to`j`

, and accumulate the sum.

```
class NumArray:
def __init__(self, nums):
self.nums = nums
def sumRange(self, i, j):
return sum(self.nums[k] for k in range(i, j + 1))
```

### Time Complexity:

O(n) per query – where n is the number of elements between indices `i`

and `j`

.

### Space Complexity:

O(1) – excluding the space needed to store the input array.

However, this approach is not efficient, especially when dealing with a large number of queries or large arrays.

## Approach 2: Prefix Sum

To optimize the `sumRange`

queries, we can preprocess the array by creating an array of prefix sums. Prefix sums can significantly reduce the time complexity of range sum queries.

- In the
`NumArray`

constructor, build an array`prefixSum`

, where`prefixSum[i]`

is the sum of elements`nums[0] + nums[1] + ... + nums[i]`

. - For the
`sumRange`

method, return`prefixSum[j] - prefixSum[i - 1]`

if`i > 0`

, else return`prefixSum[j]`

.

```
class NumArray:
def __init__(self, nums):
self.prefixSum = [0] * (len(nums) + 1)
for i in range(1, len(nums) + 1):
self.prefixSum[i] = self.prefixSum[i - 1] + nums[i - 1]
def sumRange(self, i, j):
return self.prefixSum[j + 1] - self.prefixSum[i]
```

### Time Complexity:

O(1) per query – Preprocessing takes O(n), but each query can be answered in constant time.

### Space Complexity:

O(n) – We are using an additional array to store the prefix sums.

## Conclusion:

The ‘Range Sum Query – Immutable’ problem on LeetCode is a staple example showcasing the power of prefix sums in optimizing range queries. By using a prefix sum array, we can reduce the time complexity of each query to constant time, making it a highly efficient solution especially when dealing with large datasets.