Solution
Approach 1: Maintain Array Sum
Intuition and Algorithm
Let's try to maintain S
, the sum of the array throughout one query operation.
When acting on an array element A[index]
, the rest of the values of A
remain the same. Let's remove A[index]
from S
if it is even, then add A[index] + val
back (if it is even.)
Here are some examples:

If we have
A = [2,2,2,2,2]
,S = 10
, and we doA[0] += 4
: we will updateS = 2
, thenS += 6
. At the end, we will haveA = [6,2,2,2,2]
andS = 14
. 
If we have
A = [1,2,2,2,2]
,S = 8
, and we doA[0] += 3
: we will skip updatingS
(sinceA[0]
is odd), thenS += 4
. At the end, we will haveA = [4,2,2,2,2]
andS = 12
. 
If we have
A = [2,2,2,2,2]
,S = 10
and we doA[0] += 1
: we will updateS = 2
, then skip updatingS
(sinceA[0] + 1
is odd.) At the end, we will haveA = [3,2,2,2,2]
andS = 8
. 
If we have
A = [1,2,2,2,2]
,S = 8
and we doA[0] += 2
: we will skip updatingS
(sinceA[0]
is odd), then skip updatingS
again (sinceA[0] + 2
is odd.) At the end, we will haveA = [3,2,2,2,2]
andS = 8
.
These examples help illustrate that our algorithm actually maintains the value of S
throughout each query operation.
Complexity Analysis

Time Complexity: , where is the length of
A
and is the number ofqueries
. 
Space Complexity: , though we only allocate additional space.
Analysis written by: @awice.