#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/range-sum-query-2d-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/range-sum-query-2d-implementation

Repovive

LeetCode 304 Range Sum Query 2D - Implementation - Prefix Sums | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 304 Range Sum Query 2D - Implementation

The code

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.