LeetCode 304 Range Sum Query 2D - Implementation

function NumMatrix(matrix)
    m := rows of matrix
    n := cols of matrix
    pref := 2D array of size (m + 1) x (n + 1), filled with 0
    // Build 2D prefix sums
    for i from 1 to m
        for j from 1 to n
            pref[i][j] := matrix[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]
function sumRegion(r1, c1, r2, c2)
    // Convert to 1-indexed
    r1++
    c1++
    r2++
    c2++
    return pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1]

Time: $O(mn)$ to build, $O(1)$ per query. Space: $O(mn)$.

The formula adds the top-left rectangle twice (once in each subtraction), so you add it back once. Visualizing the four rectangles makes this clear.