2D Range Sum - Build

Here's how to build the 2D prefix array:

function build2DPrefix(matrix)
    rows := number of rows in matrix
    cols := number of cols in matrix
    prefix := 2D array of size (rows + 1) x (cols + 1), all zeros

    for i from 1 to rows
        for j from 1 to cols
            prefix[i][j] := matrix[i-1][j-1]
                          + prefix[i-1][j]
                          + prefix[i][j-1]
                          - prefix[i-1][j-1]
    return prefix

Time: $O(nm)$. Space: $O(nm)$.