# LeetCode 370: Range Addition

## Problem Restatement

We are given an array of length `length`.

Initially, every element is `0`.

We are also given a list of update operations. Each update has this form:

```python
[startIndex, endIndex, inc]
```

For each update, add `inc` to every index from `startIndex` to `endIndex`, inclusive.

After all updates are applied, return the final array.

The update range is inclusive, and the official example is `length = 5`, `updates = [[1,3,2],[2,4,3],[0,2,-2]]`, with output `[-2,0,3,5,3]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `length` and list of updates |
| Update format | `[startIndex, endIndex, inc]` |
| Initial array | All zeroes |
| Output | Final array after all updates |
| Range rule | `startIndex` and `endIndex` are inclusive |

Example function shape:

```python
def getModifiedArray(length: int, updates: list[list[int]]) -> list[int]:
    ...
```

## Examples

Example:

```python
length = 5
updates = [
    [1, 3, 2],
    [2, 4, 3],
    [0, 2, -2],
]
```

Start with:

```python
[0, 0, 0, 0, 0]
```

Apply the first update:

```python
[1, 3, 2]
```

Add `2` from index `1` to index `3`:

```python
[0, 2, 2, 2, 0]
```

Apply the second update:

```python
[2, 4, 3]
```

Add `3` from index `2` to index `4`:

```python
[0, 2, 5, 5, 3]
```

Apply the third update:

```python
[0, 2, -2]
```

Add `-2` from index `0` to index `2`:

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

So the answer is:

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

## First Thought: Apply Each Update Directly

The most direct solution is to keep the array and apply every update element by element.

```python
class Solution:
    def getModifiedArray(self, length: int, updates: list[list[int]]) -> list[int]:
        nums = [0] * length

        for start, end, inc in updates:
            for i in range(start, end + 1):
                nums[i] += inc

        return nums
```

This is easy to understand.

But it can be slow.

If there are many updates and each update covers a large range, the same indices are updated again and again.

With `m` updates and array length `n`, this can take:

```python
O(m * n)
```

We need to avoid touching every element for every update.

## Key Insight

Use a difference array.

Instead of applying an increment to every index in a range, mark where the increment starts and where it stops.

For an update:

```python
[start, end, inc]
```

we do:

```python
diff[start] += inc
```

This means:

```text
from this index onward, add inc
```

Then, if `end + 1` is inside the array:

```python
diff[end + 1] -= inc
```

This means:

```text
after the range ends, cancel inc
```

After all updates are marked, the final array is the prefix sum of `diff`.

## Difference Array Example

Use:

```python
length = 5
updates = [[1, 3, 2]]
```

Start with:

```python
diff = [0, 0, 0, 0, 0]
```

Mark the start:

```python
diff[1] += 2
```

Now:

```python
[0, 2, 0, 0, 0]
```

Mark the position after the end:

```python
diff[4] -= 2
```

Now:

```python
[0, 2, 0, 0, -2]
```

Take prefix sums:

| Index | Running sum | Final value |
|---:|---:|---:|
| `0` | `0` | `0` |
| `1` | `2` | `2` |
| `2` | `2` | `2` |
| `3` | `2` | `2` |
| `4` | `0` | `0` |

Final array:

```python
[0, 2, 2, 2, 0]
```

That is exactly the direct update result.

## Algorithm

1. Create a difference array:

```python
diff = [0] * length
```

2. For each update `[start, end, inc]`:
   - Add `inc` at `start`.
   - Subtract `inc` at `end + 1` if that index exists.

3. Convert the difference array into the final array by prefix sum.

4. Return the final array.

## Correctness

For each update `[start, end, inc]`, the algorithm adds `inc` to `diff[start]`.

When we later compute prefix sums, this `inc` contributes to every index from `start` onward.

If `end + 1` is inside the array, the algorithm subtracts `inc` at `diff[end + 1]`.

During prefix-sum reconstruction, this subtraction cancels the earlier increment starting at `end + 1`.

Therefore, the update contributes exactly `inc` to indices from `start` through `end`, and contributes `0` outside that range.

Because addition is commutative, all range updates can be marked first and then combined with one prefix sum pass.

So the final array produced by the algorithm is exactly the array obtained by applying every update directly.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | `length` |
| `m` | Number of updates |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m)` | Mark each update once, then scan the array once |
| Space | `O(n)` | Difference array stores `n` values |

This improves over the direct `O(n * m)` approach.

## Implementation

```python
class Solution:
    def getModifiedArray(self, length: int, updates: list[list[int]]) -> list[int]:
        diff = [0] * length

        for start, end, inc in updates:
            diff[start] += inc

            if end + 1 < length:
                diff[end + 1] -= inc

        running = 0

        for i in range(length):
            running += diff[i]
            diff[i] = running

        return diff
```

## Code Explanation

We create the difference array:

```python
diff = [0] * length
```

For every update, mark the start of the increment:

```python
diff[start] += inc
```

Then mark where the increment should stop:

```python
if end + 1 < length:
    diff[end + 1] -= inc
```

The boundary check matters when the update reaches the final index.

For example:

```python
[start, end, inc] = [2, 4, 3]
length = 5
```

The range ends at index `4`, so `end + 1 = 5` is outside the array. There is no later index where we need to cancel the increment.

Then we build the final array with a running prefix sum:

```python
running = 0

for i in range(length):
    running += diff[i]
    diff[i] = running
```

We reuse `diff` as the output array to avoid allocating another list.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.getModifiedArray(
        5,
        [[1, 3, 2], [2, 4, 3], [0, 2, -2]],
    ) == [-2, 0, 3, 5, 3]

    assert s.getModifiedArray(
        10,
        [[2, 4, 6], [5, 6, 8], [1, 9, -4]],
    ) == [0, -4, 2, 2, 2, 4, 4, -4, -4, -4]

    assert s.getModifiedArray(
        3,
        [],
    ) == [0, 0, 0]

    assert s.getModifiedArray(
        1,
        [[0, 0, 5], [0, 0, -2]],
    ) == [3]

    assert s.getModifiedArray(
        5,
        [[0, 4, 10]],
    ) == [10, 10, 10, 10, 10]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks overlapping positive and negative updates |
| Longer example | Checks multiple disjoint and overlapping ranges |
| No updates | Array should remain all zeroes |
| Single-element array | Checks boundary handling |
| Full-range update | Checks missing `end + 1` cancellation |