LeetCode 304 Range Sum Query 2D - Immutable - Implementation

Build 2D prefix sums in constructor. Answer queries with inclusion-exclusion.

class NumMatrix: function init(matrix): m, n = len(matrix), len(matrix[0]) self.prefix = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): self.prefix[i+1][j+1] = (matrix[i][j] + self.prefix[i][j+1] + self.prefix[i+1][j] - self.prefix[i][j])

function sumRegion(r1, c1, r2, c2):
    return (self.prefix[r2+1][c2+1]
        - self.prefix[r1][c2+1]
        - self.prefix[r2+1][c1]
        + self.prefix[r1][c1])

$O(mn)$ preprocessing, $O(1)$ per query, $O(mn)$ space.