Table of Contents

## Problem Statement

In this problem, we are given an array of integer and array of arrays *queries. *For the *ith* query, we will have two parameters, *index *and *val. *After each query, we add *val* to array[index]. We need to find the sum of all **even** integers in the array after each query, and return it as a vector of integers.

### Example

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

8 6 2 4

A = [1,2,3,4], queries = [[2,0],[-2,2],[6,0],[4,2]]

6 6 6 6

## Approach

### Implementation of Sum of Even Numbers After Queries

One basic approach would be:

For each query, update the corresponding element, and then traverse through the whole array to find the sum of all even numbers. But, this approach would take O(N) time for each query leading to O(N * Q) overall time.

We can do better by maintaining a *pre sum *which is the sum of all even numbers in the array. For each query, we can check whether the element at its index was contributing to the* even sum* calculated earlier(by checking if A[index] % 2 == 0). If yes, we subtract it from the running sum and update A[index] as A[index] + val. After that, we need to again check if A[index] is even. If yes, we add it to *even_sum. *This will be the answer for that query as all the other even elements stay unaffected. Hence, we answer each query in O(1) time.

#### C++ Program

#include <bits/stdc++.h> using namespace std; vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) { int evenSum = 0; for(int &x : A) { if(x % 2 == 0) { evenSum += x; } } int n = queries.size() , val , idx; vector <int> ans(n); for(int i = 0 ; i < n ; i++) { val = queries[i][0] , idx = queries[i][1]; if(A[idx] % 2 == 0) evenSum -= A[idx]; A[idx] += val; if(A[idx] % 2 == 0) evenSum += A[idx]; ans[i] = evenSum; } return ans; } int main() { vector <int> A = {1 , 2 , 3 , 4}; vector < vector <int> > queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}}; vector <int> ans = sumEvenAfterQueries(A , queries); for(int &x : ans) cout << x << " "; cout << endl; return 0; }

#### Java Program

class sum_even_after_queries { public static void main(String args[]) { int[] A = {1 , 2 , 3 , 4}; int[][] queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}}; int[] ans = sumEvenAfterQueries(A , queries); for(int x : ans) System.out.print(x + " "); System.out.println(); } public static int[] sumEvenAfterQueries(int[] A, int[][] queries) { int evenSum = 0; for(int x : A) { if(x % 2 == 0) { evenSum += x; } } int n = queries.length , val , idx; int[] ans = new int[n]; for(int i = 0 ; i < n ; i++) { val = queries[i][0]; idx = queries[i][1]; if(A[idx] % 2 == 0) evenSum -= A[idx]; A[idx] += val; if(A[idx] % 2 == 0) evenSum += A[idx]; ans[i] = evenSum; } return ans; } }

8 6 2 4

### Complexity Analysis of Sum of Even Numbers After Queries

**Time Complexity**

**O(N + Q)**, where, N = size of the given array. Q = number of queries. We spend O(N) time to find the *even sum *and O(Q) time to answer each query.

**Space Complexity **

**O(1)**, as we use constant memory space.