Find Number of even subarrays $O(n)$ [explanation needed]

Question

So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must be even or even + even or odd + odd. However, I am not sure how this person manages to take into account the fact that these subarrays need to be contiguous and how just tracking the number of cumulative sums that are even/odd as you iterate through the array is good enough

Outlining his algorithm:

• initialize sum, odds to 0 and evens to 1.
• iterate through the array.
  • at each index i, do sum = (sum + A[i]) % 2
    • if sum is 0, increment evens, else increment odds
• Lastly, return (evens * (evens - 1) / 2) + (odds * (odds - 1) / 2)

The algorithm works... I just have no idea how.

Answer 1

Let $S_i$ be the sum of the array upto index $i$. Then we can directly calculate the sum of any contiguous subarray $x_i, x_{i+1}, ..., x_{j}$ using the expression $S_j - S_{i-1}$. This subarray will have even sum only if $S_{i-1}$ and $S_j$ are both even or both odd.

With this in mind, we can count how many even and odd $S_i$ we have and then calculate the number of possible pairs of $S_i$ and $S_j$ that yield an even number. So if we have $e$ even $S_i$ then there are $e \choose 2$ possible pairs. Each pair, corresponds to a different contiguous subarray.

$$ {e \choose 2} = \frac{e!}{(e-2)!2!} = \frac{e * (e-1)}{2} $$

Same holds for the pair of odds.