2D Prefix - The Formula

To query the sum of a rectangle from $(r_1, c_1)$ to $(r_2, c_2)$: $sum = prefix[r_2+1][c_2+1] - prefix[r_1][c_2+1] - prefix[r_2+1][c_1] + prefix[r_1][c_1]$ Why four terms?

You start with the big rectangle, subtract two overlapping pieces, but that removes the top-left corner twice. Add it back once. You're using inclusion-exclusion.

Draw it on paper if it's not clear. The picture makes the formula obvious.