I solved it in a different way than described in the editorial.

First of all, notice that for any rectangle with even lengths, odd sum and even sum are completely symmetric. Thus, for some $$$2n \times 2m$$$ matrix we can take the answer as just $$$sum / 2$$$.

Then, if either width or height of a rectangle is odd, you could separately add one row and one column to the answer. If both of them are odd, don't forget to subtract the contribution of one cell in the border because we count it twice.

I developed a mathematical formula for the sum of the given matrix(with replaced zeros) encompassing the rectangle (1,1) to (i,j) say f(i,j)

then answer for query (a,b,c,d) is simply f(c,d) — f(b,c-1) — f(a-1,d) + f(a-1,b-1);[see geometrically]

1. Calculating f(i,j) was all math
2. value at (i,j) is either 0 or (i−1)×M + j
3. total contributions at i,j can be divided into those coming from (i-1)*M term and those from + j term
4. for contributions from j we see that even indices rows given same contribution
5. for contributions from i just do a little math