Extending to 2D

What if you have a matrix instead of an array? Can you answer submatrix sum queries in $O(1)$? Yes. The same idea applies, but you need inclusion-exclusion to avoid double-counting. For a 2D prefix sum, $prefix[i][j]$ stores the sum of all elements in the rectangle from $(0, 0)$ to $(i-1, j-1)$.