Define pref[i][j] as the sum of all elements in the rectangle from (0,0) to (i−1,j−1). To build it: pref[i][j]=matrix[i−1][j−1]+pref[i−1][j]+pref[i][j−1]−pref[i−1][j−1] You add the top and left rectangles, but they overlap at the top-left corner, so you subtract it once.
To query a rectangle from (r1,c1) to (r2,c2): pref[r2+1][c2+1]−pref[r1][c2+1]−pref[r2+1][c1]+pref[r1][c1] Same inclusion-exclusion principle.