# LeetCode 985: Sum of Even Numbers After Queries

## Problem Restatement

We are given an integer array `nums` and an array `queries`.

Each query has the form:

```python
[val, index]
```

For each query, we update the array:

```python
nums[index] = nums[index] + val
```

After that update, we need to record the sum of all even values in `nums`.

Return an array where each element is the even-number sum after the corresponding query.

Each query permanently changes `nums`. The next query uses the modified array. The problem statement defines each query as `[val_i, index_i]` and asks for the sum of even values after applying that update.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and query array `queries` |
| Query | `[val, index]` means add `val` to `nums[index]` |
| Output | Array of even sums after each query |
| Important detail | Updates are permanent |

Function shape:

```python
def sumEvenAfterQueries(nums: list[int], queries: list[list[int]]) -> list[int]:
    ...
```

## Examples

Example 1:

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

Initial even values are:

```python
2 + 4 = 6
```

Process each query:

| Query | Updated `nums` | Even sum |
|---|---|---:|
| `[1, 0]` | `[2, 2, 3, 4]` | `8` |
| `[-3, 1]` | `[2, -1, 3, 4]` | `6` |
| `[-4, 0]` | `[-2, -1, 3, 4]` | `2` |
| `[2, 3]` | `[-2, -1, 3, 6]` | `4` |

Answer:

```python
[8, 6, 2, 4]
```

## First Thought: Recompute the Sum Each Time

The direct approach is simple.

For every query:

1. Update the target element.
2. Scan the full array.
3. Add up all even numbers.
4. Store the result.

```python
class Solution:
    def sumEvenAfterQueries(
        self,
        nums: list[int],
        queries: list[list[int]],
    ) -> list[int]:
        answer = []

        for val, index in queries:
            nums[index] += val

            even_sum = 0
            for num in nums:
                if num % 2 == 0:
                    even_sum += num

            answer.append(even_sum)

        return answer
```

This is correct, but it repeats unnecessary work.

## Problem With Recomputing

Each query changes only one element.

If `nums` has `n` elements and there are `q` queries, rescanning the whole array after every query costs:

```python
O(n * q)
```

We can do better by maintaining the sum of even values as a running value.

## Key Insight

Only one number changes per query.

So the even sum can only change because of that one number.

Before updating `nums[index]`:

- If it is even, remove its old value from the running sum.
- If it is odd, it contributes nothing.

Then apply the update.

After updating `nums[index]`:

- If it is even, add its new value to the running sum.
- If it is odd, it contributes nothing.

This gives `O(1)` work per query.

## Algorithm

First compute:

```python
even_sum = sum(num for num in nums if num % 2 == 0)
```

Then process each query `[val, index]`.

For each query:

1. If `nums[index]` is even, subtract it from `even_sum`.
2. Add `val` to `nums[index]`.
3. If the new `nums[index]` is even, add it to `even_sum`.
4. Append `even_sum` to the answer.

## Correctness

At the start, `even_sum` is the sum of all even values in `nums`.

For each query, only `nums[index]` changes. All other elements keep the same parity and value, so their contribution to the even sum stays unchanged.

If the old value at `nums[index]` is even, the algorithm subtracts it before the update. This removes its old contribution. If the old value is odd, it contributed nothing, so no subtraction is needed.

After the update, if the new value is even, the algorithm adds it. This includes its new contribution. If the new value is odd, it contributes nothing.

Therefore, after each query, `even_sum` equals the sum of all even values in the updated array. The algorithm appends this value after every query, so the returned array is correct.

## Complexity

Let `n = len(nums)` and `q = len(queries)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + q)` | Compute the initial even sum once, then process each query in constant time |
| Space | `O(q)` | The answer array stores one result per query |

Ignoring the output array, the extra space is `O(1)`.

## Implementation

```python
class Solution:
    def sumEvenAfterQueries(
        self,
        nums: list[int],
        queries: list[list[int]],
    ) -> list[int]:
        even_sum = 0

        for num in nums:
            if num % 2 == 0:
                even_sum += num

        answer = []

        for val, index in queries:
            if nums[index] % 2 == 0:
                even_sum -= nums[index]

            nums[index] += val

            if nums[index] % 2 == 0:
                even_sum += nums[index]

            answer.append(even_sum)

        return answer
```

## Code Explanation

We first compute the sum of all even values:

```python
even_sum = 0

for num in nums:
    if num % 2 == 0:
        even_sum += num
```

Then we process each query:

```python
for val, index in queries:
```

Before changing the value, remove its old contribution if it is even:

```python
if nums[index] % 2 == 0:
    even_sum -= nums[index]
```

Then apply the query:

```python
nums[index] += val
```

After the update, add the new contribution if the value is even:

```python
if nums[index] % 2 == 0:
    even_sum += nums[index]
```

Finally, store the current even sum:

```python
answer.append(even_sum)
```

## Testing

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

    assert s.sumEvenAfterQueries(
        [1, 2, 3, 4],
        [[1, 0], [-3, 1], [-4, 0], [2, 3]],
    ) == [8, 6, 2, 4]

    assert s.sumEvenAfterQueries(
        [1],
        [[4, 0]],
    ) == []

    assert s.sumEvenAfterQueries(
        [2],
        [[1, 0], [1, 0]],
    ) == [0, 4]

    assert s.sumEvenAfterQueries(
        [0, 0],
        [[1, 0], [2, 1], [-1, 0]],
    ) == [0, 2, 2]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[1,2,3,4]` with standard queries | `[8,6,2,4]` | Main example |
| `[1]`, `[[4,0]]` | `[0]` | Odd becomes odd after adding even |
| `[2]`, `[[1,0],[1,0]]` | `[0,4]` | Even to odd, then odd to even |
| `[0,0]`, `[[1,0],[2,1],[-1,0]]` | `[0,2,2]` | Handles zero and negative update |