# LeetCode 303: Range Sum Query - Immutable

## Problem Restatement

We are given an integer array `nums`.

We need to implement a class called `NumArray` that supports range sum queries.

The class has two operations:

| Operation | Meaning |
|---|---|
| `NumArray(nums)` | Build the object from the array |
| `sumRange(left, right)` | Return the sum of `nums[left] + nums[left + 1] + ... + nums[right]` |

The query range is inclusive, so both `left` and `right` are included.

The array does not change after initialization. That is why the problem says immutable. The official problem asks for many range sum queries on the same array.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Query input | Two indices `left` and `right` |
| Output | Sum of all elements from index `left` to index `right`, inclusive |
| Constraint | `0 <= left <= right < nums.length` |
| Key property | `nums` does not change |

Class shape:

```python
class NumArray:

    def __init__(self, nums: list[int]):
        ...

    def sumRange(self, left: int, right: int) -> int:
        ...
```

## Examples

Example:

```python
nums = [-2, 0, 3, -5, 2, -1]
numArray = NumArray(nums)
```

Query 1:

```python
numArray.sumRange(0, 2)
```

This asks for:

```python
nums[0] + nums[1] + nums[2]
```

So:

```python
-2 + 0 + 3 = 1
```

Output:

```python
1
```

Query 2:

```python
numArray.sumRange(2, 5)
```

This asks for:

```python
3 + (-5) + 2 + (-1)
```

Output:

```python
-1
```

Query 3:

```python
numArray.sumRange(0, 5)
```

This asks for the whole array sum.

```python
-2 + 0 + 3 + (-5) + 2 + (-1) = -3
```

Output:

```python
-3
```

## First Thought: Sum Each Query Directly

The simplest implementation stores the original array.

Then for every query, loop from `left` to `right` and add the numbers.

```python
class NumArray:

    def __init__(self, nums: list[int]):
        self.nums = nums

    def sumRange(self, left: int, right: int) -> int:
        total = 0

        for i in range(left, right + 1):
            total += self.nums[i]

        return total
```

This is correct.

But each query may scan many elements.

If the array length is `n`, one query can cost `O(n)` time. Since the problem allows many calls to `sumRange`, this can become slow.

## Key Insight

The array never changes.

So we can do extra work once in the constructor, then answer each query quickly.

Use prefix sums.

A prefix sum array stores the sum of elements before each position.

For example:

```python
nums = [-2, 0, 3, -5, 2, -1]
```

Build:

```python
prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
prefix[3] = nums[0] + nums[1] + nums[2]
```

So the full prefix array is:

| Index | `prefix[index]` | Meaning |
|---|---:|---|
| `0` | `0` | Sum before index `0` |
| `1` | `-2` | Sum of `nums[0]` |
| `2` | `-2` | Sum of `nums[0..1]` |
| `3` | `1` | Sum of `nums[0..2]` |
| `4` | `-4` | Sum of `nums[0..3]` |
| `5` | `-2` | Sum of `nums[0..4]` |
| `6` | `-3` | Sum of `nums[0..5]` |

The important formula is:

```python
sum(nums[left:right + 1]) = prefix[right + 1] - prefix[left]
```

`prefix[right + 1]` includes everything from index `0` through `right`.

`prefix[left]` includes everything before `left`.

Subtracting removes the part before `left`, leaving only the requested range.

## Algorithm

During initialization:

1. Create `prefix` with one starting value, `0`.
2. Keep a running sum.
3. For each number in `nums`, add it to the running sum.
4. Append the running sum to `prefix`.

During `sumRange(left, right)`:

1. Read `prefix[right + 1]`.
2. Read `prefix[left]`.
3. Return their difference.

## Correctness

Let `prefix[i]` be the sum of the first `i` elements of `nums`.

That means:

```python
prefix[i] = nums[0] + nums[1] + ... + nums[i - 1]
```

For a query `sumRange(left, right)`, we want:

```python
nums[left] + nums[left + 1] + ... + nums[right]
```

`prefix[right + 1]` contains:

```python
nums[0] + nums[1] + ... + nums[left - 1] + nums[left] + ... + nums[right]
```

`prefix[left]` contains:

```python
nums[0] + nums[1] + ... + nums[left - 1]
```

When we subtract `prefix[left]` from `prefix[right + 1]`, all elements before `left` cancel out.

The remaining value is exactly:

```python
nums[left] + nums[left + 1] + ... + nums[right]
```

Therefore, `sumRange` returns the correct range sum.

## Complexity

| Operation | Time | Space | Why |
|---|---:|---:|---|
| Constructor | `O(n)` | `O(n)` | Build one prefix value per array element |
| `sumRange` | `O(1)` | `O(1)` | Answer with two array reads and one subtraction |

The stored prefix array has length `n + 1`.

## Implementation

```python
class NumArray:

    def __init__(self, nums: list[int]):
        self.prefix = [0]

        running = 0
        for num in nums:
            running += num
            self.prefix.append(running)

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

## Code Explanation

The constructor starts with:

```python
self.prefix = [0]
```

This extra leading zero makes the range formula clean.

Without it, queries starting at index `0` need special handling.

Then we build the prefix array:

```python
running = 0
for num in nums:
    running += num
    self.prefix.append(running)
```

After processing each number, `running` stores the sum of all numbers seen so far.

For `sumRange`, we return:

```python
self.prefix[right + 1] - self.prefix[left]
```

The `right + 1` index is used because `prefix[k]` stores the sum of the first `k` elements, not the sum up to index `k`.

## Testing

```python
def run_tests():
    arr = NumArray([-2, 0, 3, -5, 2, -1])

    assert arr.sumRange(0, 2) == 1
    assert arr.sumRange(2, 5) == -1
    assert arr.sumRange(0, 5) == -3

    single = NumArray([7])
    assert single.sumRange(0, 0) == 7

    zeros = NumArray([0, 0, 0])
    assert zeros.sumRange(0, 2) == 0
    assert zeros.sumRange(1, 1) == 0

    mixed = NumArray([5, -3, 8, -2])
    assert mixed.sumRange(0, 0) == 5
    assert mixed.sumRange(1, 3) == 3
    assert mixed.sumRange(0, 3) == 8

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style example | Checks normal range queries |
| Single element | Checks smallest valid array |
| All zeros | Checks neutral values |
| Query starting at `0` | Confirms leading-zero prefix works |
| Query ending at last index | Confirms right boundary handling |
| Negative numbers | Confirms sums work with subtraction |