# Sum of Even Numbers After Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-even-numbers-after-queries)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-even-numbers-after-queries
**Data structures:** Array
**Companies:** [Indeed](https://scaleengineer.com/companies/indeed)
---
## Problem
You are given an integer array `nums` and an array `queries` where `queries[i] = [vali, indexi]`.

For each query `i`, first, apply `nums[indexi] = nums[indexi] + vali`, then print the sum of the even values of `nums`.

Return _an integer array_ `answer` _where_ `answer[i]` _is the answer to the_ `ith` _query_.

**Example 1:**

**Input:** nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
**Output:** [8,6,2,4]
**Explanation:** At the beginning, the array is [1,2,3,4].
After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

**Example 2:**

**Input:** nums = [1], queries = [[4,0]]
**Output:** [0]

**Constraints:**

* `1 <= nums.length <= 104`
* `-104 <= nums[i] <= 104`
* `1 <= queries.length <= 104`
* `-104 <= vali <= 104`
* `0 <= indexi < nums.length`

# Approaches
## Brute Force: Recalculate Sum for Each Query
This approach directly simulates the process described in the problem. For each query, it first updates the element in the `nums` array and then iterates through the entire modified array to calculate the sum of all even numbers. This process is repeated for every single query.
**Time:** O(N * Q), where N is the length of `nums` and Q is the length of `queries`. For each of the Q queries, we iterate through all N elements of the `nums` array to calculate the sum. · **Space:** O(Q) or O(1). We need an array of size Q to store the answers. If the output array is not considered extra space, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Directly follows the problem statement.
**Cons:** Inefficient for large inputs, as it performs a lot of redundant calculations.; Likely to result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
The core idea is to treat each query independently. We loop through the `queries` array. Inside the loop, for a given query `[val, index]`, we first perform the update `nums[index] += val`. After the update, we initialize a temporary sum variable to zero. We then loop through all elements of the `nums` array. For each element, we check if it's even using the modulo operator (`%`). If it is, we add its value to our temporary sum. Once this inner loop is complete, the temporary sum holds the total sum of even numbers for the current state of the array, which we then store in our result array. This is straightforward but inefficient because we repeatedly scan the entire `nums` array.
```java
class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int[] answer = new int[queries.length];
        
        for (int i = 0; i < queries.length; i++) {
            int val = queries[i][0];
            int index = queries[i][1];
            
            // Apply the query
            nums[index] += val;
            
            // Calculate the sum of even numbers
            int currentEvenSum = 0;
            for (int num : nums) {
                if (num % 2 == 0) {
                    currentEvenSum += num;
                }
            }
            
            // Store the result for this query
            answer[i] = currentEvenSum;
        }
        
        return answer;
    }
}
```
### Algorithm
- Initialize an integer array `answer` with the same length as `queries`.
- Iterate through each query `[val, index]` from `i = 0` to `queries.length - 1`.
- Update the `nums` array: `nums[index] = nums[index] + val`.
- Initialize a variable `currentEvenSum = 0`.
- Iterate through each number `num` in the `nums` array.
- If `num` is even (`num % 2 == 0`), add it to `currentEvenSum`.
- After the inner loop, store the result: `answer[i] = currentEvenSum`.
- Return the `answer` array after the outer loop finishes.

## Optimized Approach: Maintain a Running Sum of Even Numbers
A more efficient approach is to avoid recalculating the sum from scratch for each query. Instead, we can pre-calculate the initial sum of even numbers in the `nums` array. Then, for each query, we intelligently update this sum based on the change made to the array, which takes constant time.
**Time:** O(N + Q), where N is the length of `nums` and Q is the length of `queries`. The initial sum calculation takes O(N) time. Then, each of the Q queries is processed in O(1) constant time. · **Space:** O(Q) or O(1). We need an array of size Q to store the answers. If the output array is not considered extra space, the space complexity is O(1) as we only use a few extra variables.
**Pros:** Highly efficient and optimal for the given constraints.; Avoids redundant computations by updating the sum incrementally.
**Cons:** Slightly more complex logic than the brute-force approach due to tracking the running sum.
### Explanation
First, we iterate through the initial `nums` array once to compute the sum of all its even numbers. Let's call this `evenSum`. Then, we process the queries one by one. For each query `[val, index]`, we look at the value at `nums[index]` *before* the update. Let's call it `oldVal`.
If `oldVal` is even, it was part of our `evenSum`, so we subtract it.
Next, we calculate the new value, `newVal = oldVal + val`, and update the array: `nums[index] = newVal`.
Now, we check if this `newVal` is even. If it is, we add it to our `evenSum`.
After adjusting `evenSum`, we store its current value as the answer for this query. This way, each query is processed in constant time, leading to a much faster overall solution.
```java
class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int[] answer = new int[queries.length];
        
        // 1. Calculate the initial sum of even numbers
        int evenSum = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                evenSum += num;
            }
        }
        
        // 2. Process each query
        for (int i = 0; i < queries.length; i++) {
            int val = queries[i][0];
            int index = queries[i][1];
            
            // Get the original value
            int oldVal = nums[index];
            
            // If the original value was even, subtract it from the sum
            if (oldVal % 2 == 0) {
                evenSum -= oldVal;
            }
            
            // Update the number in the array
            int newVal = oldVal + val;
            nums[index] = newVal;
            
            // If the new value is even, add it to the sum
            if (newVal % 2 == 0) {
                evenSum += newVal;
            }
            
            // Store the current even sum as the answer for this query
            answer[i] = evenSum;
        }
        
        return answer;
    }
}
```
### Algorithm
- Initialize a variable `evenSum = 0`.
- Iterate through the initial `nums` array. If a number is even, add it to `evenSum`.
- Initialize an integer array `answer` with the same length as `queries`.
- Iterate through each query `[val, index]` from `i = 0` to `queries.length - 1`.
- Store the original value: `oldVal = nums[index]`.
- If `oldVal` is even, subtract it from `evenSum`: `evenSum -= oldVal`.
- Calculate the new value: `newVal = oldVal + val`.
- Update the array: `nums[index] = newVal`.
- If `newVal` is even, add it to `evenSum`: `evenSum += newVal`.
- Store the updated sum in the result array: `answer[i] = evenSum`.
- Return the `answer` array.

# Solutions
### CSharp

```csharp
public class Solution { public int [] SumEvenAfterQueries ( int [] nums , int [][] queries ) { int s = nums . Where ( x => x % 2 == 0 ). Sum (); int [] ans = new int [ queries . Length ]; for ( int j = 0 ; j < queries . Length ; j ++) { int v = queries [ j ][ 0 ], i = queries [ j ][ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans [ j ] = s ; } return ans ; } }
```

### Java

```java
class Solution { public int [] sumEvenAfterQueries ( int [] nums , int [][] queries ) { int s = 0 ; for ( int x : nums ) { if ( x % 2 == 0 ) { s += x ; } } int m = queries . length ; int [] ans = new int [ m ]; int k = 0 ; for ( var q : queries ) { int v = q [ 0 ], i = q [ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans [ k ++] = s ; } return ans ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number[][]} queries * @return {number[]} */ var sumEvenAfterQueries =
  function (nums, queries) {
    let s = 0;
    for (const x of nums) {
      if (x % 2 === 0) {
        s += x;
      }
    }
    const ans = [];
    for (const [v, i] of queries) {
      if (nums[i] % 2 === 0) {
        s -= nums[i];
      }
      nums[i] += v;
      if (nums[i] % 2 === 0) {
        s += nums[i];
      }
      ans.push(s);
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: vector < int > sumEvenAfterQueries ( vector < int >& nums , vector < vector < int >>& queries ) { int s = 0 ; for ( int x : nums ) { if ( x % 2 == 0 ) { s += x ; } } vector < int > ans ; for ( auto & q : queries ) { int v = q [ 0 ], i = q [ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans . push_back ( s ); } return ans ; } };
```

### Python

```python
class Solution : def sumEvenAfterQueries ( self , nums : List [ int ], queries : List [ List [ int ]] ) -> List [ int ]: s = sum ( x for x in nums if x % 2 == 0 ) ans = [] for v , i in queries : if nums [ i ] % 2 == 0 : s -= nums [ i ] nums [ i ] += v if nums [ i ] % 2 == 0 : s += nums [ i ] ans . append ( s ) return ans
```