Sum of Even Numbers After Queries

medium array simulation running sum

Problem

You are given an integer array nums and an array queries where queries[i] = [val, index]. For each query, add val to nums[index], then report the sum of the even values of nums after that update. Return an array answer where answer[i] is the answer to the i-th query.

Inputnums = [1, 2, 3, 4], queries = [[1,0],[-3,1],[-4,0],[2,3]]

Output[8, 6, 2, 4]

After [1,0], nums = [2,2,3,4], even sum = 2+2+4 = 8. After [-3,1], nums = [2,-1,3,4], even sum = 2+4 = 6. After [-4,0], nums = [-2,-1,3,4], even sum = -2+4 = 2. After [2,3], nums = [-2,-1,3,6], even sum = -2+6 = 4.

nums (comma-separated)

queries (val:index, ...)

def sum_even_after_queries(nums, queries):
    even_sum = sum(x for x in nums if x % 2 == 0)
    answer = []
    for val, idx in queries:
        if nums[idx] % 2 == 0:
            even_sum -= nums[idx]
        nums[idx] += val
        if nums[idx] % 2 == 0:
            even_sum += nums[idx]
        answer.append(even_sum)
    return answer

function sumEvenAfterQueries(nums, queries) {
  let evenSum = 0;
  for (const x of nums) if (x % 2 === 0) evenSum += x;
  const answer = [];
  for (const [val, idx] of queries) {
    if (nums[idx] % 2 === 0) evenSum -= nums[idx];
    nums[idx] += val;
    if (nums[idx] % 2 === 0) evenSum += nums[idx];
    answer.push(evenSum);
  }
  return answer;
}

class Solution {
    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int evenSum = 0;
        for (int x : nums) if (x % 2 == 0) evenSum += x;
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int val = queries[i][0], idx = queries[i][1];
            if (nums[idx] % 2 == 0) evenSum -= nums[idx];
            nums[idx] += val;
            if (nums[idx] % 2 == 0) evenSum += nums[idx];
            answer[i] = evenSum;
        }
        return answer;
    }
}

vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
    int evenSum = 0;
    for (int x : nums) if (x % 2 == 0) evenSum += x;
    vector<int> answer;
    for (auto& q : queries) {
        int val = q[0], idx = q[1];
        if (nums[idx] % 2 == 0) evenSum -= nums[idx];
        nums[idx] += val;
        if (nums[idx] % 2 == 0) evenSum += nums[idx];
        answer.push_back(evenSum);
    }
    return answer;
}

Explanation

The naive approach re-scans the whole array after every query to add up the even numbers, which is slow. The trick is to keep a running total of even values and only adjust it for the one element that changed.

First we compute even_sum once by adding every even value in nums. From then on, each query only touches one index, so the even sum can only change because of that one cell.

For each query we do a tidy three-step update on the target index. If the old value was even, we subtract it out first (it is about to change). Then we apply the update nums[idx] += val. Finally, if the new value is even, we add it back in. We record the current even_sum as that query's answer.

This works because the even sum stays correct after every step: we always remove the stale contribution and add the fresh one, never touching the other elements.

Example: nums=[1,2,3,4] has even sum 6. Query [1,0] makes nums[0]=2 (odd 1 had no contribution, add 2), so even sum becomes 8 — the first answer.

Time: O(n + q) Space: O(1)